oj.uz

Submission #212622

# Submission time Handle Problem Language Result Execution time Memory
212622 2020-03-23T20:23:01 Z MarcoMeijer Mechanical Doll (IOI18_doll) C++14
100 / 100
 174 ms 10736 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
 
//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int n, s, root;
vi c, x, y, a, state;
 
int LOG2(int _X) {
  int cur=1, cnt=0;
  while(1) {
    if(cur >= _X) return cnt;
    cnt++;
    cur *= 2;
  }
}
int createTriangle(int size) {
  if(size == 0) return 0;
  int i=s++;
  int id = -s;
  int nx = createTriangle(size-1);
  int ny = createTriangle(size-1);
  x[i] = nx;
  y[i] = ny;
  return id;
}
void setTriangle(int u, int value) {
  u = -1-u;
  if(state[u]) {
    state[u] = !state[u];
    if(y[u] == 0) y[u] = value;
    else setTriangle(y[u], value);
  } else {
    state[u] = !state[u];
    if(x[u] == 0) x[u] = value;
    else setTriangle(x[u], value);
  }
}
void create(int size) {
  int l2 = LOG2(size)+1;
  s = l2;
  root = -s;
  REV(i,0,l2) {
    int u  = i;
    int id = -u-1;
    int nx, ny;
    if(i == 0) ny = 0;
    else ny = id+1;
    if(size&(1<<i)) {
      nx = createTriangle(i);
    } else {
      nx = root;
    }
    x[u] = nx;
    y[u] = ny;
  }
}
 
void create_circuit(int m, vi A) {
  a = A;
  s = 0;
  n = a.size();
  c.clear(); x.clear(); y.clear(); state.clear();
  int mx=3e5;
  x.resize(mx);
  y.resize(mx);
  state.resize(mx);
  RE(i,mx) state[i]=0;
 
  create(n);
  RE(i,n) setTriangle(root, a[i]);
 
  c.resize(m+1);
  RE(i,m+1) c[i] = root;

  x.resize(s);
  y.resize(s);
 
  answer(c, x, y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3788 KB Output is correct
2 Correct 59 ms 6868 KB Output is correct
3 Correct 60 ms 6392 KB Output is correct
4 Correct 4 ms 3788 KB Output is correct
5 Correct 14 ms 4940 KB Output is correct
6 Correct 80 ms 7780 KB Output is correct
7 Correct 4 ms 3788 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3788 KB Output is correct
2 Correct 59 ms 6868 KB Output is correct
3 Correct 60 ms 6392 KB Output is correct
4 Correct 4 ms 3788 KB Output is correct
5 Correct 14 ms 4940 KB Output is correct
6 Correct 80 ms 7780 KB Output is correct
7 Correct 4 ms 3788 KB Output is correct
8 Correct 104 ms 8340 KB Output is correct
9 Correct 114 ms 8808 KB Output is correct
10 Correct 174 ms 10736 KB Output is correct
11 Correct 3 ms 3788 KB Output is correct
12 Correct 2 ms 3788 KB Output is correct
13 Correct 3 ms 3788 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3788 KB Output is correct
2 Correct 59 ms 6868 KB Output is correct
3 Correct 60 ms 6392 KB Output is correct
4 Correct 4 ms 3788 KB Output is correct
5 Correct 14 ms 4940 KB Output is correct
6 Correct 80 ms 7780 KB Output is correct
7 Correct 4 ms 3788 KB Output is correct
8 Correct 104 ms 8340 KB Output is correct
9 Correct 114 ms 8808 KB Output is correct
10 Correct 174 ms 10736 KB Output is correct
11 Correct 3 ms 3788 KB Output is correct
12 Correct 2 ms 3788 KB Output is correct
13 Correct 3 ms 3788 KB Output is correct
14 Correct 153 ms 10332 KB Output is correct
15 Correct 99 ms 7964 KB Output is correct
16 Correct 139 ms 10180 KB Output is correct
17 Correct 3 ms 3788 KB Output is correct
18 Correct 3 ms 3788 KB Output is correct
19 Correct 3 ms 3788 KB Output is correct
20 Correct 166 ms 10540 KB Output is correct
21 Correct 3 ms 3788 KB Output is correct
22 Correct 3 ms 3788 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3788 KB Output is correct
2 Correct 106 ms 7340 KB Output is correct
3 Correct 94 ms 7300 KB Output is correct
4 Correct 151 ms 9272 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3788 KB Output is correct
2 Correct 106 ms 7340 KB Output is correct
3 Correct 94 ms 7300 KB Output is correct
4 Correct 151 ms 9272 KB Output is correct
5 Correct 150 ms 10076 KB Output is correct
6 Correct 152 ms 9868 KB Output is correct
7 Correct 141 ms 9992 KB Output is correct
8 Correct 160 ms 9576 KB Output is correct
9 Correct 88 ms 7404 KB Output is correct
10 Correct 148 ms 9480 KB Output is correct
11 Correct 136 ms 9240 KB Output is correct
12 Correct 102 ms 7472 KB Output is correct
13 Correct 89 ms 7716 KB Output is correct
14 Correct 108 ms 7776 KB Output is correct
15 Correct 100 ms 7908 KB Output is correct
16 Correct 7 ms 3944 KB Output is correct
17 Correct 87 ms 7408 KB Output is correct
18 Correct 88 ms 7416 KB Output is correct
19 Correct 113 ms 7408 KB Output is correct
20 Correct 137 ms 9316 KB Output is correct
21 Correct 140 ms 9268 KB Output is correct
22 Correct 140 ms 9236 KB Output is correct