oj.uz

Submission #784808

# Submission time Handle Problem Language Result Execution time Memory
784808 2023-07-16T14:43:51 Z QwertyPi Mechanical Doll (IOI18_doll) C++14
100 / 100
 93 ms 13668 KB 
#include "doll.h"
#include <bits/stdc++.h>

const int SLOT = 1234567;
const int MAXN = 2e5 + 1111;
using namespace std; 

int S = 0;
int MX[MAXN], MY[MAXN]; 
bool T[MAXN];
int build(int lv, int n){
	if(n == 0) return 0;
	if(lv == 0) return SLOT;
	int sr = min(n, 1 << lv - 1), sl = n - sr; 
	int vl = build(lv - 1, sl);
	int vr = build(lv - 1, sr);
	int v = --S;
	MX[-v] = vl, MY[-v] = vr;
	return v;
}

void create_circuit(int M, vector<int> A) {
  A.push_back(0);
  int N = A.size();
  std::vector<int> C(M + 1);
  int level = 0; int x = N; while(x > (1 << level)) level++;
  build(level, N);
  int root = S;
  C[0] = root;
  for (int i = 1; i <= M; ++i) {
    C[i] = root;
  }
  for(int i = 0; i < MAXN; i++) if(MX[i] == 0) MX[i] = root;
  for(int i = 0; i < MAXN; i++) if(MY[i] == 0) MY[i] = root;
  int cur = 0, filled = 0;
  while(filled < N){
  	if(cur >= 0) cur = C[cur];
	  else {
	  	cur = -cur;
  		if(T[cur] && MY[cur] == SLOT) MY[cur] = A[filled++];
  		if(!T[cur] && MX[cur] == SLOT) MX[cur] = A[filled++];
  		int nxt = T[cur] ? MY[cur] : MX[cur]; T[cur] ^= 1;
  		cur = nxt;
	}
  }
  
  std::vector<int> X(-S), Y(-S);
  for (int k = 0; k < -S; ++k) {
  	X[k] = MX[k + 1], Y[k] = MY[k + 1];
  }
  answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'int build(int, int)':
doll.cpp:14:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   14 |  int sr = min(n, 1 << lv - 1), sl = n - sr;
      |                       ~~~^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 34 ms 5572 KB Output is correct
3 Correct 30 ms 5696 KB Output is correct
4 Correct 1 ms 1876 KB Output is correct
5 Correct 8 ms 3028 KB Output is correct
6 Correct 46 ms 7868 KB Output is correct
7 Correct 1 ms 1876 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 34 ms 5572 KB Output is correct
3 Correct 30 ms 5696 KB Output is correct
4 Correct 1 ms 1876 KB Output is correct
5 Correct 8 ms 3028 KB Output is correct
6 Correct 46 ms 7868 KB Output is correct
7 Correct 1 ms 1876 KB Output is correct
8 Correct 58 ms 9460 KB Output is correct
9 Correct 61 ms 10108 KB Output is correct
10 Correct 90 ms 13668 KB Output is correct
11 Correct 2 ms 1876 KB Output is correct
12 Correct 1 ms 1840 KB Output is correct
13 Correct 1 ms 1840 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 34 ms 5572 KB Output is correct
3 Correct 30 ms 5696 KB Output is correct
4 Correct 1 ms 1876 KB Output is correct
5 Correct 8 ms 3028 KB Output is correct
6 Correct 46 ms 7868 KB Output is correct
7 Correct 1 ms 1876 KB Output is correct
8 Correct 58 ms 9460 KB Output is correct
9 Correct 61 ms 10108 KB Output is correct
10 Correct 90 ms 13668 KB Output is correct
11 Correct 2 ms 1876 KB Output is correct
12 Correct 1 ms 1840 KB Output is correct
13 Correct 1 ms 1840 KB Output is correct
14 Correct 87 ms 12880 KB Output is correct
15 Correct 55 ms 8772 KB Output is correct
16 Correct 88 ms 12580 KB Output is correct
17 Correct 1 ms 1876 KB Output is correct
18 Correct 2 ms 1876 KB Output is correct
19 Correct 2 ms 1844 KB Output is correct
20 Correct 87 ms 13204 KB Output is correct
21 Correct 1 ms 1876 KB Output is correct
22 Correct 2 ms 1876 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 50 ms 6720 KB Output is correct
3 Correct 60 ms 7684 KB Output is correct
4 Correct 77 ms 10848 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 50 ms 6720 KB Output is correct
3 Correct 60 ms 7684 KB Output is correct
4 Correct 77 ms 10848 KB Output is correct
5 Correct 83 ms 12436 KB Output is correct
6 Correct 93 ms 11952 KB Output is correct
7 Correct 89 ms 12080 KB Output is correct
8 Correct 80 ms 11660 KB Output is correct
9 Correct 52 ms 7680 KB Output is correct
10 Correct 82 ms 11648 KB Output is correct
11 Correct 88 ms 11276 KB Output is correct
12 Correct 52 ms 7932 KB Output is correct
13 Correct 58 ms 8388 KB Output is correct
14 Correct 55 ms 8548 KB Output is correct
15 Correct 55 ms 8644 KB Output is correct
16 Correct 3 ms 1980 KB Output is correct
17 Correct 50 ms 7932 KB Output is correct
18 Correct 53 ms 7916 KB Output is correct
19 Correct 51 ms 7840 KB Output is correct
20 Correct 81 ms 11508 KB Output is correct
21 Correct 81 ms 11156 KB Output is correct
22 Correct 79 ms 11240 KB Output is correct