oj.uz

Submission #130413

# Submission time Handle Problem Language Result Execution time Memory
130413 2019-07-15T07:17:22 Z rondojim Mechanical Doll (IOI18_doll) C++17
100 / 100
 126 ms 10448 KB 
#include "doll.h"

using namespace std;

int n;
int seg[1 << 19];

int bitRev(int x, int n) {
  int r = 0;
  while (n >>= 1) {
    r <<= 1;
    r ^= (x & 1);
    x >>= 1;
  }
  return r;
}

const int inf = 1e9;

void create_circuit(int m, vector<int> A) {
  int sz = 1;
  A.push_back(0);
  n = A.size();
  while (sz < n) sz <<= 1;
  for(int i = 0; i < sz; ++i) seg[i + sz] = inf;
  for(int i = 0, j = 0; i < sz; ++i){
    int k = bitRev(i, sz);
    if(k < sz - n) continue;
    seg[k + sz] = A[j++];
  }
  int SN = 0;
  vector<int> X, Y;
  
  for(int i = sz; --i;){
    if (seg[i << 1] == seg[i << 1 | 1]){
      seg[i] = seg[i << 1];
      continue;
    }
    int S = SN++;
    seg[i] = -(S + 1);
    X.push_back(seg[i << 1]);
    Y.push_back(seg[i << 1 | 1]);
  }
  for(int i = 0; i < SN; ++i) {
    if(X[i] == inf) X[i] = seg[1];
    if(Y[i] == inf) Y[i] = seg[1];
  }
  answer(vector<int>(m + 1, seg[1]), X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 39 ms 4932 KB Output is correct
3 Correct 35 ms 4904 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 972 KB Output is correct
6 Correct 50 ms 6632 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 39 ms 4932 KB Output is correct
3 Correct 35 ms 4904 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 972 KB Output is correct
6 Correct 50 ms 6632 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 68 ms 7524 KB Output is correct
9 Correct 107 ms 8156 KB Output is correct
10 Correct 89 ms 10448 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 39 ms 4932 KB Output is correct
3 Correct 35 ms 4904 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 972 KB Output is correct
6 Correct 50 ms 6632 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 68 ms 7524 KB Output is correct
9 Correct 107 ms 8156 KB Output is correct
10 Correct 89 ms 10448 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 126 ms 9916 KB Output is correct
15 Correct 61 ms 6980 KB Output is correct
16 Correct 89 ms 9652 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 89 ms 10128 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 24 ms 3320 KB Output is correct
3 Correct 30 ms 3228 KB Output is correct
4 Correct 44 ms 3876 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 24 ms 3320 KB Output is correct
3 Correct 30 ms 3228 KB Output is correct
4 Correct 44 ms 3876 KB Output is correct
5 Correct 83 ms 9444 KB Output is correct
6 Correct 93 ms 9176 KB Output is correct
7 Correct 82 ms 9220 KB Output is correct
8 Correct 84 ms 8880 KB Output is correct
9 Correct 65 ms 6340 KB Output is correct
10 Correct 71 ms 8176 KB Output is correct
11 Correct 75 ms 8484 KB Output is correct
12 Correct 69 ms 7572 KB Output is correct
13 Correct 73 ms 6700 KB Output is correct
14 Correct 66 ms 6752 KB Output is correct
15 Correct 56 ms 6976 KB Output is correct
16 Correct 4 ms 532 KB Output is correct
17 Correct 73 ms 6680 KB Output is correct
18 Correct 51 ms 7576 KB Output is correct
19 Correct 70 ms 7700 KB Output is correct
20 Correct 83 ms 8720 KB Output is correct
21 Correct 75 ms 8500 KB Output is correct
22 Correct 78 ms 8484 KB Output is correct