oj.uz

Submission #136143

# Submission time Handle Problem Language Result Execution time Memory
136143 2019-07-24T19:23:04 Z forelax Sequence (BOI14_sequence) C++14
0 / 100
 129 ms 944 KB 
#include<bits/stdc++.h>
using namespace std;
long long ask(vector<int> req,long long pw,long long cn){
//    cout<<req.size()<<" "<<pw<<" "<<cn<<endl;
    if(req.size()==1){
        long long num=0;
        int rq=req[0];
        bool first=rq&1;
        for(int i = 1 ; i < 10 ; i ++){
            if(rq&(1<<i)){
                num*=10;
                num+=i;
                if(first){
                    num*=10;
                    first=false;
                }
            }
        }
        if(first)num=10;
        return cn+num*pw;
    }
    bool need=false;
    for(int i = 0 ; i < req.size() ; i ++)
        if(req[i])need=true;
    if(!need){
        return cn+(cn==0?pw:0);
    }
    long long rez=-1;
    for(int dg=0;dg<10;dg++){
        vector<int> treq;
        bool use=false;
        for(int i = 0,ng=dg,sw=true ; i < req.size() ; i ++,ng=(ng+1)%10){
            if(sw)treq.push_back(0);
            int rq=req[i];
            if(rq&(1<<ng)){
                rq-=1<<ng;
                use=true;
            }
            treq.back()|=rq;
            sw=(ng==9);
        }
        if(!use)continue;
        long long b=ask(treq,pw*10,cn+pw*dg);
        if(rez==-1||b<rez)rez=b;
    }
    return rez;
}
int main(){
    int n;
    cin>>n;
    vector<int> v(n);
    vector<int> req(n);
    for(int i = 0 ; i < n ; i ++){
        cin>>v[i];
        req[i]=1<<v[i];
    }
    cout<<ask(req,1,0);
}

Compilation message

sequence.cpp: In function 'long long int ask(std::vector<int>, long long int, long long int)':
sequence.cpp:23:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < req.size() ; i ++)
                     ~~^~~~~~~~~~~~
sequence.cpp:32:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0,ng=dg,sw=true ; i < req.size() ; i ++,ng=(ng+1)%10){
                                       ~~^~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 380 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Incorrect 2 ms 256 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 20 ms 504 KB Output is correct
3 Correct 20 ms 376 KB Output is correct
4 Incorrect 21 ms 504 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 129 ms 944 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Incorrect 2 ms 376 KB Output isn't correct
8 Halted 0 ms 0 KB -