oj.uz

Submission #258225

# Submission time Handle Problem Language Result Execution time Memory
258225 2020-08-05T15:00:21 Z cheeheng Devil's Share (RMI19_devil) C++14
56 / 100
 1500 ms 2168 KB 
#include <bits/stdc++.h>
using namespace std;

int D[12];
int X[100005];
int ans[100005];

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

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

        int S = 0;
        for(int i = 1; i < 10; i ++){
            scanf("%d", &D[i]);
            S += D[i];
        }

        int cnt = 0;
        for(int i = 1; i < 10; i ++){
            for(int j = 0; j < D[i]; j ++){
                X[cnt++] = i;
            }
        }
        sort(X, X+S);

        bool subtask3 = true;
        for(int i = 3; i < 10; i ++){
            subtask3 &= (D[i] == 0);
        }

        if(K == 2){
            for(int i = 0; i < S; i ++){
                if(i%2 == 0){
                    ans[i] = X[S-1-i/2];
                }else{
                    ans[i] = X[i/2];
                }
            }

            reverse(ans, ans+S);

            for(int i = 0; i < S; i ++){
                printf("%d", ans[i]);
            }
            printf("\n");
            continue;
        }

        if(subtask3){
            if(D[2] < K || D[1] == 0){
                for(int i = 0; i < S; i ++){
                    printf("%d", X[i]);
                }
                printf("\n");
            }else{
                int num1 = D[1];
                int num2 = D[2]-K+1;
                int numConsecutive2 = 1+(num2-1)/num1;

                for(int i = 0; i <= S-K; i ++){
                    ans[S-K-i] = 2 - ((((long long)i*num1+num1-1) %(num1+num2)) < num1);
                }

                for(int i = S-K+1; i <= S; i ++){
                    ans[i] = 2;
                }

                /*
                long long tempMax = 0;
                for(int i = 0; i <= S-K; i ++){
                    long long temp = 0;
                    for(int j = i; j < i+K; j ++){
                        temp = temp*10+ans[j];
                    }
                    //printf("%lld\n", temp);
                    tempMax = max(tempMax, temp);
                }
                printf("tempMax=%lld\n", tempMax);
                */

                for(int i = 0; i < S; i ++){
                    printf("%d", ans[i]);
                }
                printf("\n");
            }
            continue;
        }

        long long minVal = 1LL << 62;
        do{
            long long tempMax = 0;

            for(int i = 0; i <= S-K; i ++){
                long long temp = 0;
                for(int j = i; j < i+K; j ++){
                    temp = temp*10+X[j];
                }
                //printf("%lld\n", temp);
                tempMax = max(tempMax, temp);
            }
            if(tempMax < minVal){
                for(int i = 0; i < S; i ++){
                    ans[i] = X[i];
                }
                minVal = tempMax;

                //printf("tempMax=%lld\n", tempMax);
            }
        }while(next_permutation(X, X+S));

        //printf("tempMax=%lld\n", minVal);

        for(int i = 0; i < S; i ++){
            printf("%d", ans[i]);
        }
        printf("\n");
    }

    return 0;
}

Compilation message

devil.cpp: In function 'int main()':
devil.cpp:62:21: warning: unused variable 'numConsecutive2' [-Wunused-variable]
                 int numConsecutive2 = 1+(num2-1)/num1;
                     ^~~~~~~~~~~~~~~
devil.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &T);
     ~~~~~^~~~~~~~~~
devil.cpp:14:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &K);
         ~~~~~^~~~~~~~~~
devil.cpp:18:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &D[i]);
             ~~~~~^~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 504 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 1416 KB Output is correct
2 Correct 115 ms 1400 KB Output is correct
3 Correct 119 ms 1528 KB Output is correct
4 Correct 139 ms 1456 KB Output is correct
5 Correct 92 ms 1272 KB Output is correct
6 Correct 93 ms 1272 KB Output is correct
7 Correct 96 ms 1400 KB Output is correct
8 Correct 94 ms 1400 KB Output is correct
9 Correct 95 ms 2032 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 1272 KB Output is correct
2 Correct 108 ms 1532 KB Output is correct
3 Correct 89 ms 2040 KB Output is correct
4 Correct 92 ms 2168 KB Output is correct
5 Correct 100 ms 2168 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 504 KB Output is correct
2 Correct 140 ms 1416 KB Output is correct
3 Correct 115 ms 1400 KB Output is correct
4 Correct 119 ms 1528 KB Output is correct
5 Correct 139 ms 1456 KB Output is correct
6 Correct 92 ms 1272 KB Output is correct
7 Correct 93 ms 1272 KB Output is correct
8 Correct 96 ms 1400 KB Output is correct
9 Correct 94 ms 1400 KB Output is correct
10 Correct 95 ms 2032 KB Output is correct
11 Correct 110 ms 1272 KB Output is correct
12 Correct 108 ms 1532 KB Output is correct
13 Correct 89 ms 2040 KB Output is correct
14 Correct 92 ms 2168 KB Output is correct
15 Correct 100 ms 2168 KB Output is correct
16 Execution timed out 1589 ms 384 KB Time limit exceeded
17 Halted 0 ms 0 KB -