oj.uz

Submission #238302

# Submission time Handle Problem Language Result Execution time Memory
238302 2020-06-10T18:06:51 Z Jatana Mechanical Doll (IOI18_doll) C++17
81.1504 / 100
 229 ms 14464 KB 
#include "doll.h"
#include <iostream>
#include <algorithm>
#include <cassert>
#include <random>

#define le(v) ((int)v.size())
#define pb push_back
using namespace std;
 
vector<int> X, Y;
 
int inc = 0;
int go(int outs) {
	int id = le(X);
	X.pb(-1e9); Y.pb(-1e9);
	if (outs > 2) {
		if (outs & 1) {
			outs++;
			inc++;
		}
		X[id] = go(outs / 2);
		Y[id] = go(outs / 2);	
	} else assert(outs == 2);
	return -(id + 1);
}
 
mt19937 rng(1337);
void create_circuit(int M, vector<int> A) {
	X.clear(); Y.clear();
	int N = A.size();
	vector<vector<int>> after(M + 1);
	vector<int> wait(M + 1);
	A.pb(0);
	for (int i = 0; i < le(A) - 1; i++) {
		after[A[i]].pb(A[i + 1]);
	}	
	A.pop_back();
	vector<int> C(M + 1);
	C[0] = A[0];
	for (int i = 1; i <= M; i++) {
		if (!after[i].empty()) {
			if (le(after[i]) == 1) {
				C[i] = after[i][0];
			} else {
				int sz = le(after[i]);
				inc = 0;
				C[i] = go(sz);
				wait[i] = inc;
			}
		}
		reverse(after[i].begin(), after[i].end());
	}
	// for (int x : wait) {
	// 	cout << x << " ";
	// }
	// return;
	int cur = C[0];
	int real = -1;
	while (cur) {
		// cerr << cur << " ";
		if (cur > 0) {
			real = cur;
			cur = C[cur];
		}	else {
			cur = (-cur) - 1;
			if (X[cur] == -1e9) {
				if (wait[real]
						&& ((le(after[real]) == 1) || ((wait[real] + le(after[real])) % 2 == 0))) {
					wait[real]--;
					X[cur] = C[real];
				} else {
					X[cur] = after[real].back();
					after[real].pop_back();
				}
			}
			swap(X[cur], Y[cur]);
			cur = Y[cur];
		}
	}
	vector<bool> del(le(X), false);
	for (int it = 0; it < 10; it++) {
		for (int i = 0; i < le(X); i++) {
			if (del[i]) continue;
			if (X[i] < 0) {
				int j = (-X[i]) - 1;
				if (X[j] == Y[j]) {
					X[i] = X[j];
					del[j] = true;
				}
			}
			if (Y[i] < 0) {
				int j = (-Y[i]) - 1;
				if (X[j] == Y[j]) {
					Y[i] = X[j];
					del[j] = true;
				}
			}
		}
		for (int i = 0; i < le(C); i++) {
			if (C[i] < 0) {
				int j = (-C[i]) - 1;
				if (X[j] == Y[j]) {
					C[i] = X[j];
					del[j] = true;
				}
			}
		}
	}
	vector<int> alive;
	for (int i = 0; i < le(X); i++) {
		if (!del[i]) {
			alive.pb(i);
		}
	}
	for (int i = 0; i < le(X); i++) {
		if (X[i] < 0) {
			int id = lower_bound(alive.begin(), alive.end(), (-X[i]) - 1) - alive.begin();
			X[i] = -(id + 1);
		}
		if (Y[i] < 0) {
			int id = lower_bound(alive.begin(), alive.end(), (-Y[i]) - 1) - alive.begin();
			Y[i] = -(id + 1);
		}
	}
	for (int i = 0; i < le(C); i++) {
		if (C[i] < 0) {
			int id = lower_bound(alive.begin(), alive.end(), (-C[i]) - 1) - alive.begin();
			C[i] = -(id + 1);
		}
	}
	int jump = 0;
	for (int i = 0; i < le(X); i++) {
		if (del[i]) {
			jump++;
		} else {
			X[i - jump] = X[i];
			Y[i - jump] = Y[i];
		}
	}
	X.resize(le(X) - jump);
	Y.resize(le(Y) - jump);
	// for (int x : del) {
	// 	cout << x << " ";
	// }
	// cout << endl;
	// for (int i = 0; i < le(X); i++) {
	// 	cout << X[i] << " " << Y[i] << endl;
	// }
	answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:31:6: warning: unused variable 'N' [-Wunused-variable]
   31 |  int N = A.size();
      |      ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 35 ms 6728 KB Output is correct
3 Correct 27 ms 5396 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 4172 KB Output is correct
6 Correct 42 ms 8104 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 35 ms 6728 KB Output is correct
3 Correct 27 ms 5396 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 4172 KB Output is correct
6 Correct 42 ms 8104 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 68 ms 7828 KB Output is correct
9 Correct 75 ms 9260 KB Output is correct
10 Correct 124 ms 12324 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 35 ms 6728 KB Output is correct
3 Correct 27 ms 5396 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 4172 KB Output is correct
6 Correct 42 ms 8104 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 68 ms 7828 KB Output is correct
9 Correct 75 ms 9260 KB Output is correct
10 Correct 124 ms 12324 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 184 ms 12056 KB Output is correct
15 Correct 75 ms 6796 KB Output is correct
16 Correct 114 ms 9516 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 137 ms 11564 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 43 ms 3632 KB Output is correct
3 Correct 72 ms 4148 KB Output is correct
4 Correct 118 ms 7220 KB Output is correct

Subtask #6
37.150369844 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 43 ms 3632 KB Output is correct
3 Correct 72 ms 4148 KB Output is correct
4 Correct 118 ms 7220 KB Output is correct
5 Partially correct 161 ms 14264 KB Output is partially correct
6 Partially correct 168 ms 14464 KB Output is partially correct
7 Partially correct 209 ms 14428 KB Output is partially correct
8 Partially correct 229 ms 13808 KB Output is partially correct
9 Correct 180 ms 6580 KB Output is correct
10 Correct 195 ms 12076 KB Output is correct
11 Partially correct 172 ms 12628 KB Output is partially correct
12 Partially correct 101 ms 7340 KB Output is partially correct
13 Partially correct 100 ms 8040 KB Output is partially correct
14 Partially correct 104 ms 8152 KB Output is partially correct
15 Partially correct 107 ms 8352 KB Output is partially correct
16 Partially correct 4 ms 560 KB Output is partially correct
17 Partially correct 110 ms 6992 KB Output is partially correct
18 Partially correct 95 ms 6780 KB Output is partially correct
19 Partially correct 109 ms 7576 KB Output is partially correct
20 Partially correct 151 ms 12320 KB Output is partially correct
21 Partially correct 178 ms 11500 KB Output is partially correct
22 Partially correct 140 ms 10632 KB Output is partially correct