Submission #794923

#	Time	Username	Problem	Language	Result	Execution time	Memory
794923		gun_gan	Sequence (BOI14_sequence)	C++17	0 / 100	8 ms	448 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> prv;

ll f(int dep) {
      if(prv.size() == 1) {
            ll res = 0;
            bool zero = 0;
            for(int i = 0; i < 10; i++) {
                  if(i == 0 && prv[0] & 1) {
                        zero = 1;
                        continue;
                  }

                  if(prv[0] >> i & 1) {
                        res = res * 10 + i;
                        if(zero) {
                              zero = 0;
                              res = res * 10;
                        }
                  }
            }

            if(!zero)
                  return res;
            else
                  return 10;
      }

      ll res = 1e18;

      for(int d = 0; d < 10; d++) {
            vector<int> nxt;

            int cur = d, i = 0, mask = 0;
            bool need = 0;
            while(i < prv.size()) {
                  if(prv[i] & (1 << cur)) {
                        mask |= prv[i] ^ (1 << cur);
                        need = 1;
                  } else mask |= prv[i];

                  cur++;
                  if(cur == 10) {
                        cur = 0;
                        nxt.push_back(mask);
                        mask = 0;
                  }
                  i++;
            }

            if(cur > 0) {
                  nxt.push_back(mask);
            }

            swap(prv, nxt);

            if(need) {
                  ll q = f(dep + 1);
                  res = min(res, q * 10 + d);
            }

            swap(prv, nxt);
      }

      return res;
}
 
int main() {
      cin.tie(0); ios_base::sync_with_stdio(0);
 
      int K;
      cin >> K;

      for(int i = 0; i < K; i++) {
            int x;
            cin >> x;
            prv.push_back(1 << x);
      }
 
      cout << f(0) << '\n';
} 

Compilation message (stderr)

sequence.cpp: In function 'll f(int)':
sequence.cpp:39:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |             while(i < prv.size()) {
      |                   ~~^~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 33
• Subtask 3: 0 / 25
• Subtask 4: 0 / 33