oj.uz

Submission #868381

# Submission time Handle Problem Language Result Execution time Memory
868381 2023-10-31T09:25:40 Z abczz Mechanical Doll (IOI18_doll) C++14
60.6719 / 100
 82 ms 7732 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;
  ll id = cnt++, mid = (l+r)/2;
  //cout << id << " " << l << " " << r << endl;
  X.push_back(-1);
  Y.push_back(-1);
  if (k-n >= r) {
    X[id] = -(id+1);
    Y[id] = -1;
    return id+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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
14.7580402392 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Output is partially correct
2 Partially correct 55 ms 5152 KB Output is partially correct
3 Partially correct 50 ms 5160 KB Output is partially correct
4 Partially correct 74 ms 7072 KB Output is partially correct

Subtask #6
45.9139029664 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Output is partially correct
2 Partially correct 55 ms 5152 KB Output is partially correct
3 Partially correct 50 ms 5160 KB Output is partially correct
4 Partially correct 74 ms 7072 KB Output is partially correct
5 Partially correct 79 ms 7732 KB Output is partially correct
6 Correct 81 ms 7436 KB Output is correct
7 Partially correct 82 ms 7564 KB Output is partially correct
8 Partially correct 76 ms 7308 KB Output is partially correct
9 Partially correct 51 ms 5304 KB Output is partially correct
10 Partially correct 77 ms 7328 KB Output is partially correct
11 Partially correct 80 ms 7020 KB Output is partially correct
12 Partially correct 50 ms 5480 KB Output is partially correct
13 Partially correct 52 ms 5908 KB Output is partially correct
14 Partially correct 52 ms 5988 KB Output is partially correct
15 Partially correct 52 ms 6072 KB Output is partially correct
16 Partially correct 2 ms 600 KB Output is partially correct
17 Correct 47 ms 4736 KB Output is correct
18 Partially correct 52 ms 5560 KB Output is partially correct
19 Partially correct 51 ms 5496 KB Output is partially correct
20 Correct 74 ms 7044 KB Output is correct
21 Partially correct 80 ms 7024 KB Output is partially correct
22 Partially correct 80 ms 7020 KB Output is partially correct