oj.uz

Submission #258140

# Submission time Handle Problem Language Result Execution time Memory
258140 2020-08-05T12:17:49 Z tqbfjotld Devil's Share (RMI19_devil) C++14
0 / 100
 1500 ms 1528 KB 
#include <bits/stdc++.h>
using namespace std;
///i have no idea what i'm doing at this point
int arr[11];

string mult(string s, int num){
    string res = "";
    for (int x = 0; x<num; x++){
        res += s;
    }
   // printf("was multing %s by %d\n",s.c_str(),num);
    return res;
}

struct compa{

bool operator()(pair<string,int> a,pair<string,int> b){
    for (int x = 0; x<min(a.first.size(),b.first.size()); x++){
        if (a.first[x]!=b.first[x]) return a.first[x]<b.first[x];
    }
    return a.first.size()>b.first.size();
}
};


int main(){
    int test;
    scanf("%d",&test);
    while (test--){
        int k,n=0;
        scanf("%d",&k);
        for (int x = 1; x<10; x++){
            scanf("%d",&arr[x]);
            n+= arr[x];
        }
        multiset<pair<string,int>,compa >s;
        string curbig = "";
        int temp = 0;
        int curnum = 0;
        for (int x = 1; x<10; x++){
            string te = "";
            te += ('0'+x);
            if (arr[x]!=0)

            temp += arr[x];
            //printf("temp is now %d\n",temp);
            if (temp>n-k&&curnum==0){
                curbig += ('0'+x);
                curnum = arr[x]-(temp-n+k-1);
                //printf("curbig should be %c\n",'0'+x);
                //printf("curbig is [%s]\n",curbig.c_str());
                if (temp-n+k-1!=0)
                s.insert({te,temp-n+k-1});
            }else s.insert({te,arr[x]});
        }
        while (curbig.size()<k && !s.empty()){
           // printf("curbig is %s, curnum is %d\n",curbig.c_str(),curnum);
            auto it = s.begin();
            //printf("first item is %s,%d\n",(*it).first.c_str(),(*it).second);
            if ((*it).first+(*it).first>curbig && curnum!=1){
                curbig = mult(curbig,curnum);
                curnum = 1;
                continue;
            }
            if ((*it).second<curnum){
                curnum -= (*it).second;
                string t = (*it).first;
                int t2 = (*it).second;
                s.erase(it);
                s.insert({curbig+t,t2});
                continue;
            }
            string t = (*it).first;
            int num = (*it).second;
            s.erase(it);
            if (num-curnum>0){
                s.insert({t,num-curnum});
            }
            curbig += t;
        }
        printf("%s",mult(curbig,curnum).c_str());
        for (auto x : s){
            printf("%s",mult(x.first,x.second).c_str());
        }
        printf("\n");
    }
}

Compilation message

devil.cpp: In member function 'bool compa::operator()(std::pair<std::__cxx11::basic_string<char>, int>, std::pair<std::__cxx11::basic_string<char>, int>)':
devil.cpp:18:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int x = 0; x<min(a.first.size(),b.first.size()); x++){
                     ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
devil.cpp: In function 'int main()':
devil.cpp:56:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (curbig.size()<k && !s.empty()){
                ~~~~~~~~~~~~~^~
devil.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&test);
     ~~~~~^~~~~~~~~~~~
devil.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&k);
         ~~~~~^~~~~~~~~
devil.cpp:33:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&arr[x]);
             ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1576 ms 1120 KB Time limit exceeded

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 1448 KB Output is correct
2 Correct 131 ms 1272 KB Output is correct
3 Correct 107 ms 1528 KB Output is correct
4 Execution timed out 1588 ms 1208 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 151 ms 1216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1576 ms 1120 KB Time limit exceeded