oj.uz

Submission #789941

# Submission time Handle Problem Language Result Execution time Memory
789941 2023-07-22T07:55:30 Z Trisanu_Das Mechanical Doll (IOI18_doll) C++17
100 / 100
 112 ms 13232 KB 
#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
 
vector<int> s, x(300005), y(300005), vis(300005);
int v, b = 1, n;
 
int dfs(int l, int r){
  if(l >= n) return -1;
  if(r - l > 1){
    int mid = (l + r) / 2, u = v++;
    y[u] = dfs(l, mid);
    x[u] = dfs(mid, r);
    return -(u + 1);
  }
  return 1;
}
 
void create_circuit(int m, vector<int> a){
  s.assign(m + 1, -1);
  a.push_back(0);
  n = a.size();
  while(b < n) b *= 2;
  dfs(0, b);
  for(int i : a){
    int u = 0;
    while(u > -1){
      vis[u] ^= 1;
      int &w = vis[u] ? x[u] : y[u];
      if(w >= 0) w = i, u = -1;
      else u = -(w + 1);
    }
  }
  x.resize(v);
  y.resize(v);
  answer(s, x, y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3796 KB Output is correct
2 Correct 37 ms 7352 KB Output is correct
3 Correct 35 ms 7228 KB Output is correct
4 Correct 2 ms 3796 KB Output is correct
5 Correct 13 ms 4948 KB Output is correct
6 Correct 56 ms 9164 KB Output is correct
7 Correct 2 ms 3796 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3796 KB Output is correct
2 Correct 37 ms 7352 KB Output is correct
3 Correct 35 ms 7228 KB Output is correct
4 Correct 2 ms 3796 KB Output is correct
5 Correct 13 ms 4948 KB Output is correct
6 Correct 56 ms 9164 KB Output is correct
7 Correct 2 ms 3796 KB Output is correct
8 Correct 69 ms 9956 KB Output is correct
9 Correct 91 ms 10440 KB Output is correct
10 Correct 108 ms 13232 KB Output is correct
11 Correct 2 ms 3796 KB Output is correct
12 Correct 2 ms 3832 KB Output is correct
13 Correct 2 ms 3796 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3796 KB Output is correct
2 Correct 37 ms 7352 KB Output is correct
3 Correct 35 ms 7228 KB Output is correct
4 Correct 2 ms 3796 KB Output is correct
5 Correct 13 ms 4948 KB Output is correct
6 Correct 56 ms 9164 KB Output is correct
7 Correct 2 ms 3796 KB Output is correct
8 Correct 69 ms 9956 KB Output is correct
9 Correct 91 ms 10440 KB Output is correct
10 Correct 108 ms 13232 KB Output is correct
11 Correct 2 ms 3796 KB Output is correct
12 Correct 2 ms 3832 KB Output is correct
13 Correct 2 ms 3796 KB Output is correct
14 Correct 100 ms 12720 KB Output is correct
15 Correct 67 ms 9360 KB Output is correct
16 Correct 104 ms 12540 KB Output is correct
17 Correct 2 ms 3796 KB Output is correct
18 Correct 2 ms 3796 KB Output is correct
19 Correct 2 ms 3796 KB Output is correct
20 Correct 112 ms 13032 KB Output is correct
21 Correct 2 ms 3796 KB Output is correct
22 Correct 2 ms 3796 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3840 KB Output is correct
2 Correct 63 ms 8456 KB Output is correct
3 Correct 66 ms 8412 KB Output is correct
4 Correct 97 ms 11052 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3840 KB Output is correct
2 Correct 63 ms 8456 KB Output is correct
3 Correct 66 ms 8412 KB Output is correct
4 Correct 97 ms 11052 KB Output is correct
5 Correct 101 ms 12364 KB Output is correct
6 Correct 103 ms 12068 KB Output is correct
7 Correct 102 ms 12184 KB Output is correct
8 Correct 100 ms 11868 KB Output is correct
9 Correct 65 ms 8460 KB Output is correct
10 Correct 94 ms 11700 KB Output is correct
11 Correct 109 ms 11432 KB Output is correct
12 Correct 66 ms 8644 KB Output is correct
13 Correct 70 ms 9096 KB Output is correct
14 Correct 64 ms 9180 KB Output is correct
15 Correct 65 ms 9328 KB Output is correct
16 Correct 3 ms 3924 KB Output is correct
17 Correct 64 ms 8664 KB Output is correct
18 Correct 66 ms 8596 KB Output is correct
19 Correct 66 ms 8644 KB Output is correct
20 Correct 100 ms 11668 KB Output is correct
21 Correct 100 ms 11312 KB Output is correct
22 Correct 97 ms 11444 KB Output is correct