/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 324.0 KiB
#2 Accepted 15ms 524.0 KiB
#3 Accepted 15ms 456.0 KiB
#4 Accepted 15ms 524.0 KiB
#5 Accepted 15ms 520.0 KiB
#6 Accepted 15ms 520.0 KiB
#7 Wrong Answer 16ms 528.0 KiB
#8 Wrong Answer 2ms 284.0 KiB
#9 Wrong Answer 1ms 284.0 KiB
#10 Wrong Answer 14ms 520.0 KiB
#11 Wrong Answer 1ms 320.0 KiB
#12 Wrong Answer 6ms 476.0 KiB
#13 Wrong Answer 18ms 476.0 KiB
#14 Wrong Answer 15ms 484.0 KiB
#15 Wrong Answer 14ms 504.0 KiB

Code

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// Utility function to concatenate two strings
char* concatenate(char* str1, char* str2) {
    char* result = (char*)malloc(strlen(str1) + strlen(str2) + 1);
    strcpy(result, str1);
    strcat(result, str2);
    return result;
}

// Function to find the maximum possible value after K operations
void findMaxAfterKOperations(int A[], int N, int K) {
    char** arr = (char**)malloc(N * sizeof(char*));
    for (int i = 0; i < N; i++) {
        arr[i] = (char*)malloc(12);  // Allocate enough space for int-to-string conversion
        sprintf(arr[i], "%d", A[i]);
    }

    for (int k = 0; k < K && N > 1; k++) {
        int bestIndex = 0;
        char* maxConcat = concatenate(arr[0], arr[1]);

        for (int i = 1; i < N - 1; i++) {
            char* tempConcat = concatenate(arr[i], arr[i + 1]);
            if (strcmp(tempConcat, maxConcat) > 0) {
                free(maxConcat);
                maxConcat = tempConcat;
                bestIndex = i;
            } else {
                free(tempConcat);
            }
        }

        // Update array with the best concatenation result
        free(arr[bestIndex]);
        arr[bestIndex] = maxConcat;
        free(arr[bestIndex + 1]);

        // Shift the array elements to the left
        for (int i = bestIndex + 1; i < N - 1; i++) {
            arr[i] = arr[i + 1];
        }
        N--;
    }

    // Find the maximum value in the final array
    char* maxVal = arr[0];
    for (int i = 1; i < N; i++) {
        if (strcmp(arr[i], maxVal) > 0) {
            maxVal = arr[i];
        }
    }

    printf("%s\n", maxVal);

    // Free allocated memory
    for (int i = 0; i < N; i++) {
        free(arr[i]);
    }
    free(arr);
}

int main() {
    int T;
    scanf("%d", &T);

    while (T--) {
        int N, K;
        scanf("%d %d", &N, &K);

        int* A = (int*)malloc(N * sizeof(int));
        for (int i = 0; i < N; i++) {
            scanf("%d", &A[i]);
        }

        findMaxAfterKOperations(A, N, K);
        free(A);
    }

    return 0;
}

Information

Submit By
Type
Submission
Problem
P1083 Number concatenation
Contest
Bangladesh 2.0
Language
C99 (GCC 13.2.0)
Submit At
2024-08-16 16:09:12
Judged At
2024-10-03 13:28:26
Judged By
Score
30
Total Time
18ms
Peak Memory
528.0 KiB