Submission #43305

#	Time	Username	Problem	Language	Result	Execution time	Memory
43305		ruhanhabib39	Sequence (BOI14_sequence)	C++14	100 / 100	293 ms	4656 KiB

sequence

#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 (stderr)

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 / 9
• Subtask 2: 33 / 33
• Subtask 3: 25 / 25
• Subtask 4: 33 / 33