oj.uz

Submission #97664

# Submission time Handle Problem Language Result Execution time Memory
97664 2019-02-17T17:00:58 Z CRE_VIOUS Mechanical Doll (IOI18_doll) C++14
100 / 100
 171 ms 14152 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
 
struct Node {
	int ty, l, r;
};
 
int N, cnts = 2; Node G[500009];
 
void create_circuit(int M, std::vector<int> A) {
	N = A.size(); N++;
	int dep = 0; for (int i = 0; i < 22; i++) { int Z = (1 << i); if (Z >= N) { dep = i; break; } }
	
	for (int i = 0; i < 500009; i++) G[i] = Node{0, -1, -1};
	
	vector<int>T; T.push_back(1);
	for (int i = dep - 1; i >= 1; i--) {
		int A = (N + (1 << i) - 1) / (1 << i); vector<int> TT;
		int AL = 0, AR = A - 1; if (A % 2 == 1) { AL++; AR++; }
		for (int j = AL; j <= AR; j++) {
			if (j % 2 == 0) {
				G[T[j / 2]].l = cnts; TT.push_back(cnts); cnts++;
			}
			else {
				G[T[j / 2]].r = cnts; TT.push_back(cnts); cnts++;
			}
		}
		T = TT;
	}
	
	int BAR = T.size() * 2;
	
	for (int i = 1; i < cnts; i++) {
		if (G[i].r >= 1 && G[i].l == -1) G[i].l = 1;
	}
	
	for (int i = 0; i < BAR; i++) {
		int cx = 1, I = 0;
		if (i == BAR - 1) I = 0;
		else if (i < A.size()) I = A[i];
		else I = -1;
		
		while (true) {
			if (G[cx].l <= -1) break;
			if (G[cx].ty == 0) { G[cx].ty ^= 1; cx = G[cx].l; }
			else { G[cx].ty ^= 1; cx = G[cx].r; }
		}
		if (G[cx].ty == 0) { G[cx].l = -I; }
		else { G[cx].r = -I; }
		G[cx].ty ^= 1;
	}
	
	vector<int>C, X, Y;
	for (int i = 0; i <= M; i++) C.push_back(-1);
	for (int i = 1; i < cnts; i++) {
		X.push_back(-G[i].l);
		Y.push_back(-G[i].r);
	}
	//cout<<"C = {"; for (int i = 0; i < C.size(); i++) { if(i) cout<<","; cout<<C[i]; } cout<<"}"<<endl;
	//cout<<"X = {"; for (int i = 0; i < X.size(); i++) { if(i) cout<<","; cout<<X[i]; } cout<<"}"<<endl;
	//cout<<"Y = {"; for (int i = 0; i < Y.size(); i++) { if(i) cout<<","; cout<<Y[i]; } cout<<"}"<<endl;
	answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:41:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   else if (i < A.size()) I = A[i];
      |            ~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6092 KB Output is correct
2 Correct 52 ms 9836 KB Output is correct
3 Correct 45 ms 9696 KB Output is correct
4 Correct 4 ms 6092 KB Output is correct
5 Correct 17 ms 7364 KB Output is correct
6 Correct 70 ms 10724 KB Output is correct
7 Correct 5 ms 6168 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6092 KB Output is correct
2 Correct 52 ms 9836 KB Output is correct
3 Correct 45 ms 9696 KB Output is correct
4 Correct 4 ms 6092 KB Output is correct
5 Correct 17 ms 7364 KB Output is correct
6 Correct 70 ms 10724 KB Output is correct
7 Correct 5 ms 6168 KB Output is correct
8 Correct 115 ms 11880 KB Output is correct
9 Correct 93 ms 12580 KB Output is correct
10 Correct 153 ms 14048 KB Output is correct
11 Correct 5 ms 6072 KB Output is correct
12 Correct 4 ms 6092 KB Output is correct
13 Correct 5 ms 6092 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6092 KB Output is correct
2 Correct 52 ms 9836 KB Output is correct
3 Correct 45 ms 9696 KB Output is correct
4 Correct 4 ms 6092 KB Output is correct
5 Correct 17 ms 7364 KB Output is correct
6 Correct 70 ms 10724 KB Output is correct
7 Correct 5 ms 6168 KB Output is correct
8 Correct 115 ms 11880 KB Output is correct
9 Correct 93 ms 12580 KB Output is correct
10 Correct 153 ms 14048 KB Output is correct
11 Correct 5 ms 6072 KB Output is correct
12 Correct 4 ms 6092 KB Output is correct
13 Correct 5 ms 6092 KB Output is correct
14 Correct 121 ms 13752 KB Output is correct
15 Correct 79 ms 12268 KB Output is correct
16 Correct 129 ms 14152 KB Output is correct
17 Correct 4 ms 6092 KB Output is correct
18 Correct 5 ms 6092 KB Output is correct
19 Correct 5 ms 6092 KB Output is correct
20 Correct 137 ms 13876 KB Output is correct
21 Correct 4 ms 6092 KB Output is correct
22 Correct 4 ms 6092 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6136 KB Output is correct
2 Correct 74 ms 11460 KB Output is correct
3 Correct 73 ms 11348 KB Output is correct
4 Correct 113 ms 12944 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6136 KB Output is correct
2 Correct 74 ms 11460 KB Output is correct
3 Correct 73 ms 11348 KB Output is correct
4 Correct 113 ms 12944 KB Output is correct
5 Correct 122 ms 14012 KB Output is correct
6 Correct 124 ms 13176 KB Output is correct
7 Correct 123 ms 13084 KB Output is correct
8 Correct 120 ms 13152 KB Output is correct
9 Correct 96 ms 11404 KB Output is correct
10 Correct 116 ms 12908 KB Output is correct
11 Correct 114 ms 12896 KB Output is correct
12 Correct 75 ms 11632 KB Output is correct
13 Correct 75 ms 11888 KB Output is correct
14 Correct 78 ms 11024 KB Output is correct
15 Correct 82 ms 11028 KB Output is correct
16 Correct 7 ms 6320 KB Output is correct
17 Correct 79 ms 10912 KB Output is correct
18 Correct 92 ms 11588 KB Output is correct
19 Correct 79 ms 11652 KB Output is correct
20 Correct 119 ms 13116 KB Output is correct
21 Correct 171 ms 12904 KB Output is correct
22 Correct 116 ms 12940 KB Output is correct