Submission #107809

# Submission time Handle Problem Language Result Execution time Memory
107809 2019-04-25T20:27:04 Z patrikpavic2 Sequence (BOI14_sequence) C++17
25 / 100
232 ms 1272 KB
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <map>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef vector < int > vi;
typedef set < int > si;

const int N = 1e5 + 500;
const int M = 1e6 + 500;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int OFF = (1 << 18);
const int LOG = 20;
const double EPS = 1e-9;
const double PI = 3.1415926535;

int n;
vi v;

ll ans(vi msk, int devet){
    ll ret = 102345678900000LL;
    if(msk.size() == 1){
        ret = 0;
        for(int i = 1;i<10;i++){
            if(((1 << i) & msk[0])){
                ret = ret * 10LL + i;
                if(ret == i && (msk[0] & 1))
                    ret *= 10LL;
            }
        }
       if((msk[0] & 1) && ret == 0) ret = 10;
   //         printf("MSK{}: ");
   // for(int x : msk){
//        printf("{");
   //     for(int i = 0;i < 10;i++) if(x & (1 << i)) printf("%d ", i);
   //     printf("} ");
   // }
    //printf("   RET %lld\n", ret);

        return ret;
    }
    for(int i = 0;i < 9 + devet;i++){
        int cur = i, dos = 0, nula = 0;
        vi nw;
        for(int j = 0;j < msk.size();j++){
            int x = msk[j];
            if(x & (1 << cur)) x ^= (1 << cur);
            dos |= x;
            if((dos & 1) && cur == 0) nula = 1;
            cur = (cur + 1) % 10;
            if(cur == 0 || j == msk.size() - 1) nw.PB(dos), dos = 0;
        }
        ll nxt = ans(nw, msk.size() > 2 || i < 9) * 10LL + i;
        if(nula && nxt == 0LL) nxt = 10LL;
        ret = min(ret, nxt);
       // printf("NXT = %lld\n", nxt);
    }
   //  printf("MSK{} :");
   // for(int x : msk){
   //     printf("{");
   //     for(int i = 0;i < 10;i++) if(x & (1 << i)) printf("%d ", i);
   //     printf("} ");
   // }
    //printf("   RET %lld\n", ret);
    if(!ret) ret = 10;
    return ret;
}

int main(){
    scanf("%d", &n);
    for(int i = 0;i < n;i++){
        int d; scanf("%d", &d);
        v.PB(1 << d);
    }
    ll fin = ans(v, 1);
    if(fin == 0) fin = 10LL;
    printf("%lld\n", fin);
    return 0;
}

Compilation message

sequence.cpp: In function 'll ans(vi, int)':
sequence.cpp:60:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j < msk.size();j++){
                       ~~^~~~~~~~~~~~
sequence.cpp:66:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(cur == 0 || j == msk.size() - 1) nw.PB(dos), dos = 0;
                            ~~^~~~~~~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
sequence.cpp:87:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int d; scanf("%d", &d);
                ~~~~~^~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 4 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 23 ms 384 KB Output is correct
3 Correct 23 ms 384 KB Output is correct
4 Correct 23 ms 384 KB Output is correct
5 Correct 24 ms 384 KB Output is correct
6 Correct 18 ms 384 KB Output is correct
7 Correct 142 ms 1016 KB Output is correct
8 Correct 97 ms 884 KB Output is correct
9 Correct 232 ms 1264 KB Output is correct
10 Correct 216 ms 1272 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 3 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -