oj.uz

Submission #97329

# Submission time Handle Problem Language Result Execution time Memory
97329 2019-02-15T08:58:07 Z E869120 Mechanical Doll (IOI18_doll) C++14
100 / 100
 156 ms 14100 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 4 ms 6092 KB Output is correct
2 Correct 54 ms 9840 KB Output is correct
3 Correct 53 ms 9736 KB Output is correct
4 Correct 5 ms 6092 KB Output is correct
5 Correct 16 ms 7364 KB Output is correct
6 Correct 68 ms 10668 KB Output is correct
7 Correct 5 ms 6092 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6092 KB Output is correct
2 Correct 54 ms 9840 KB Output is correct
3 Correct 53 ms 9736 KB Output is correct
4 Correct 5 ms 6092 KB Output is correct
5 Correct 16 ms 7364 KB Output is correct
6 Correct 68 ms 10668 KB Output is correct
7 Correct 5 ms 6092 KB Output is correct
8 Correct 101 ms 11868 KB Output is correct
9 Correct 94 ms 12644 KB Output is correct
10 Correct 142 ms 14008 KB Output is correct
11 Correct 4 ms 6092 KB Output is correct
12 Correct 5 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 4 ms 6092 KB Output is correct
2 Correct 54 ms 9840 KB Output is correct
3 Correct 53 ms 9736 KB Output is correct
4 Correct 5 ms 6092 KB Output is correct
5 Correct 16 ms 7364 KB Output is correct
6 Correct 68 ms 10668 KB Output is correct
7 Correct 5 ms 6092 KB Output is correct
8 Correct 101 ms 11868 KB Output is correct
9 Correct 94 ms 12644 KB Output is correct
10 Correct 142 ms 14008 KB Output is correct
11 Correct 4 ms 6092 KB Output is correct
12 Correct 5 ms 6092 KB Output is correct
13 Correct 5 ms 6092 KB Output is correct
14 Correct 117 ms 13804 KB Output is correct
15 Correct 79 ms 12296 KB Output is correct
16 Correct 117 ms 14100 KB Output is correct
17 Correct 6 ms 6092 KB Output is correct
18 Correct 6 ms 6092 KB Output is correct
19 Correct 6 ms 6092 KB Output is correct
20 Correct 133 ms 13912 KB Output is correct
21 Correct 6 ms 6092 KB Output is correct
22 Correct 5 ms 6092 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6092 KB Output is correct
2 Correct 71 ms 11448 KB Output is correct
3 Correct 77 ms 11408 KB Output is correct
4 Correct 116 ms 12936 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6092 KB Output is correct
2 Correct 71 ms 11448 KB Output is correct
3 Correct 77 ms 11408 KB Output is correct
4 Correct 116 ms 12936 KB Output is correct
5 Correct 122 ms 14004 KB Output is correct
6 Correct 135 ms 13064 KB Output is correct
7 Correct 116 ms 13236 KB Output is correct
8 Correct 116 ms 13144 KB Output is correct
9 Correct 73 ms 11376 KB Output is correct
10 Correct 117 ms 12976 KB Output is correct
11 Correct 150 ms 12900 KB Output is correct
12 Correct 88 ms 11680 KB Output is correct
13 Correct 80 ms 12056 KB Output is correct
14 Correct 113 ms 11020 KB Output is correct
15 Correct 79 ms 11048 KB Output is correct
16 Correct 7 ms 6348 KB Output is correct
17 Correct 72 ms 10864 KB Output is correct
18 Correct 85 ms 11628 KB Output is correct
19 Correct 72 ms 11644 KB Output is correct
20 Correct 128 ms 13024 KB Output is correct
21 Correct 123 ms 12912 KB Output is correct
22 Correct 156 ms 12924 KB Output is correct