oj.uz

Submission #868382

# Submission time Handle Problem Language Result Execution time Memory
868382 2023-10-31T09:51:03 Z abczz Mechanical Doll (IOI18_doll) C++14
100 / 100
 93 ms 10808 KB 
#include "doll.h"
#include <iostream>
#include <array>
#include <vector>
#define ll int

using namespace std;

ll n, k, cnt;
bool B[400000];
vector <ll> C, X, Y;
ll solve(ll l, ll r) {
  if (l == r && k-n < l) return 0;
  //cout << id << " " << l << " " << r << endl;
  if (k-n >= r) return 1;
  ll id = cnt++, mid = (l+r)/2;
  X.push_back(-1);
  Y.push_back(-1);
  X[id] = -solve(l, mid);
  Y[id] = -solve(mid+1, r);
  //cout << id+1 << " * " << X[id] << " " << Y[id] << endl;
  return id+1;
}

void get(ll x) {
  //cout << x << " ";
  x *= -1;
  --x;
  if (!B[x]) {
    B[x] ^= 1;
    if (X[x] != 0) get(X[x]);
    else {
      X[x] = k;
      return;
    }
  }
  else {
    B[x] ^= 1;
    if (Y[x] != 0) get(Y[x]);
    else {
      Y[x] = k;
      return;
    }
  }
}

void create_circuit(int M, std::vector<int> A) {
  n = A.size() + 1;
  for (int i=0; i<=M; ++i) C.push_back(-1);
  for (int i=18; i>=0; --i) {
    if (n <= (1LL << i)) k = (1LL << i);
  }
  solve(1, k);
  for (int i=1; i<n; ++i) {
    k = A[i-1];
    get(-1);
    //cout << endl;
  }
  k = 0;
  get(-1);
  answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 30 ms 4896 KB Output is correct
3 Correct 30 ms 5008 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 8 ms 1748 KB Output is correct
6 Correct 42 ms 5848 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 30 ms 4896 KB Output is correct
3 Correct 30 ms 5008 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 8 ms 1748 KB Output is correct
6 Correct 42 ms 5848 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 56 ms 7624 KB Output is correct
9 Correct 63 ms 8128 KB Output is correct
10 Correct 84 ms 10808 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 30 ms 4896 KB Output is correct
3 Correct 30 ms 5008 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 8 ms 1748 KB Output is correct
6 Correct 42 ms 5848 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 56 ms 7624 KB Output is correct
9 Correct 63 ms 8128 KB Output is correct
10 Correct 84 ms 10808 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 85 ms 10432 KB Output is correct
15 Correct 53 ms 7020 KB Output is correct
16 Correct 81 ms 9276 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 90 ms 10652 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 1 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 50 ms 5308 KB Output is correct
3 Correct 49 ms 5316 KB Output is correct
4 Correct 82 ms 7104 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 50 ms 5308 KB Output is correct
3 Correct 49 ms 5316 KB Output is correct
4 Correct 82 ms 7104 KB Output is correct
5 Correct 87 ms 7884 KB Output is correct
6 Correct 93 ms 7308 KB Output is correct
7 Correct 79 ms 7428 KB Output is correct
8 Correct 92 ms 7292 KB Output is correct
9 Correct 48 ms 5160 KB Output is correct
10 Correct 78 ms 7316 KB Output is correct
11 Correct 76 ms 7020 KB Output is correct
12 Correct 56 ms 5572 KB Output is correct
13 Correct 51 ms 5912 KB Output is correct
14 Correct 52 ms 6076 KB Output is correct
15 Correct 52 ms 6068 KB Output is correct
16 Correct 2 ms 600 KB Output is correct
17 Correct 50 ms 4820 KB Output is correct
18 Correct 52 ms 5564 KB Output is correct
19 Correct 50 ms 5512 KB Output is correct
20 Correct 82 ms 7036 KB Output is correct
21 Correct 76 ms 6976 KB Output is correct
22 Correct 78 ms 7024 KB Output is correct