oj.uz

Submission #43305

# Submission time Handle Problem Language Result Execution time Memory
43305 2018-03-13T11:53:09 Z ruhanhabib39 Sequence (BOI14_sequence) C++14
100 / 100
 293 ms 4656 KB 
#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;

long long solve(vector<int> has, bool nineOk) {
   int K = has.size();
   if(K == 1) {
      long long res = 0;
      for(int d = 1; d <= 9; d++) {
         if(has[0] & (1 << d)) res = 10 * res + d;
         if(res == d && (has[0] & 1)) res *= 10;
      }
      if(!res && (has[0] & 1)) res = 10;
      return res;
   } else {
      long long res = INF;
      for(int d = 0; d < 9+int(nineOk); d++) {
         vector<int> nhas;
         int cd = d, st = 0;
         bool zero = false;
         for(int i = 0; i < K; i++) {
            st |= has[i] & ~(1 << cd);
            if((has[i] & 1) && cd == 0) zero = true;
            cd = (cd + 1) % 10;
            if(cd == 0 || i == K - 1) {
               nhas.push_back(st);
               st = 0;
            }
         }
         long long nres = solve(nhas, d < 9 || K > 2); // d == 9 and k == 2 -> cycle
         long long rr = 10*nres + d;
         if(zero && !rr) rr = 10;
         res = min(res, rr);
      }
      return res;
   }
}

int main() {
   int K; scanf("%d", &K);
   vector<int> has(K);
   for(int& a : has) {
      scanf("%d", &a);
      a = 1 << a;
   }
   printf("%lld\n", solve(has, true));
}

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:41:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int K; scanf("%d", &K);
                          ^
sequence.cpp:44:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &a);
                      ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 2 ms 700 KB Output is correct
5 Correct 2 ms 700 KB Output is correct
6 Correct 2 ms 700 KB Output is correct
7 Correct 2 ms 700 KB Output is correct
8 Correct 4 ms 700 KB Output is correct
9 Correct 2 ms 712 KB Output is correct
10 Correct 4 ms 752 KB Output is correct
11 Correct 4 ms 756 KB Output is correct
12 Correct 2 ms 756 KB Output is correct
13 Correct 2 ms 756 KB Output is correct
14 Correct 5 ms 756 KB Output is correct
15 Correct 4 ms 772 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 772 KB Output is correct
2 Correct 3 ms 780 KB Output is correct
3 Correct 2 ms 780 KB Output is correct
4 Correct 2 ms 780 KB Output is correct
5 Correct 2 ms 780 KB Output is correct
6 Correct 2 ms 780 KB Output is correct
7 Correct 4 ms 780 KB Output is correct
8 Correct 3 ms 780 KB Output is correct
9 Correct 5 ms 812 KB Output is correct
10 Correct 2 ms 812 KB Output is correct
11 Correct 5 ms 820 KB Output is correct
12 Correct 4 ms 820 KB Output is correct
13 Correct 3 ms 820 KB Output is correct
14 Correct 2 ms 820 KB Output is correct
15 Correct 3 ms 836 KB Output is correct
16 Correct 7 ms 836 KB Output is correct
17 Correct 4 ms 836 KB Output is correct
18 Correct 3 ms 836 KB Output is correct
19 Correct 2 ms 848 KB Output is correct
20 Correct 4 ms 852 KB Output is correct
21 Correct 3 ms 852 KB Output is correct
22 Correct 4 ms 864 KB Output is correct
23 Correct 4 ms 868 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 868 KB Output is correct
2 Correct 62 ms 880 KB Output is correct
3 Correct 31 ms 900 KB Output is correct
4 Correct 32 ms 1068 KB Output is correct
5 Correct 32 ms 1068 KB Output is correct
6 Correct 23 ms 1068 KB Output is correct
7 Correct 193 ms 1676 KB Output is correct
8 Correct 126 ms 1676 KB Output is correct
9 Correct 277 ms 2288 KB Output is correct
10 Correct 260 ms 2484 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2484 KB Output is correct
2 Correct 3 ms 2484 KB Output is correct
3 Correct 2 ms 2484 KB Output is correct
4 Correct 2 ms 2484 KB Output is correct
5 Correct 123 ms 2484 KB Output is correct
6 Correct 2 ms 2484 KB Output is correct
7 Correct 1 ms 2484 KB Output is correct
8 Correct 4 ms 2484 KB Output is correct
9 Correct 2 ms 2484 KB Output is correct
10 Correct 4 ms 2484 KB Output is correct
11 Correct 266 ms 2808 KB Output is correct
12 Correct 268 ms 3072 KB Output is correct
13 Correct 2 ms 3072 KB Output is correct
14 Correct 4 ms 3072 KB Output is correct
15 Correct 4 ms 3072 KB Output is correct
16 Correct 4 ms 3072 KB Output is correct
17 Correct 2 ms 3072 KB Output is correct
18 Correct 2 ms 3072 KB Output is correct
19 Correct 4 ms 3072 KB Output is correct
20 Correct 5 ms 3072 KB Output is correct
21 Correct 2 ms 3072 KB Output is correct
22 Correct 2 ms 3072 KB Output is correct
23 Correct 4 ms 3072 KB Output is correct
24 Correct 3 ms 3072 KB Output is correct
25 Correct 4 ms 3072 KB Output is correct
26 Correct 4 ms 3072 KB Output is correct
27 Correct 31 ms 3072 KB Output is correct
28 Correct 32 ms 3072 KB Output is correct
29 Correct 33 ms 3072 KB Output is correct
30 Correct 32 ms 3072 KB Output is correct
31 Correct 23 ms 3072 KB Output is correct
32 Correct 201 ms 3072 KB Output is correct
33 Correct 133 ms 3072 KB Output is correct
34 Correct 282 ms 3616 KB Output is correct
35 Correct 293 ms 3860 KB Output is correct
36 Correct 196 ms 3884 KB Output is correct
37 Correct 265 ms 4156 KB Output is correct
38 Correct 166 ms 4156 KB Output is correct
39 Correct 273 ms 4460 KB Output is correct
40 Correct 270 ms 4656 KB Output is correct