oj.uz

Submission #796023

# Submission time Handle Problem Language Result Execution time Memory
796023 2023-07-28T04:46:01 Z gun_gan Sequence (BOI14_sequence) C++17
0 / 100
 49 ms 700 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> prv;

ll f(int dep, bool cond) {
      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);
            }

            if(nxt == prv) continue;

            swap(prv, nxt);

            ll q = f(dep + 1, 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, 1) << '\n';
}

Compilation message

sequence.cpp: In function 'll f(int, bool)':
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()) {
      |                   ~~^~~~~~~~~~~~
sequence.cpp:38:18: warning: variable 'need' set but not used [-Wunused-but-set-variable]
   38 |             bool need = 0;
      |                  ^~~~

Subtask #1
0 / 9.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 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 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 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

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

Subtask #4
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 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 49 ms 700 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 1 ms 328 KB Output isn't correct
8 Halted 0 ms 0 KB -