oj.uz

Submission #794925

# Submission time Handle Problem Language Result Execution time Memory
794925 2023-07-27T04:08:16 Z gun_gan Sequence (BOI14_sequence) C++17
0 / 100
 8 ms 432 KB 
#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);
}

Compilation message

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.0

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

Subtask #2
0 / 33.0

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

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 8 ms 432 KB Output is correct
3 Correct 8 ms 340 KB Output is correct
4 Incorrect 8 ms 432 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

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