oj.uz

Submission #238303

# Submission time Handle Problem Language Result Execution time Memory
238303 2020-06-10T18:07:22 Z Jatana Mechanical Doll (IOI18_doll) C++17
81.1504 / 100
 285 ms 14428 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 < 100; 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 42 ms 6708 KB Output is correct
3 Correct 31 ms 5320 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 18 ms 4172 KB Output is correct
6 Correct 60 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 42 ms 6708 KB Output is correct
3 Correct 31 ms 5320 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 18 ms 4172 KB Output is correct
6 Correct 60 ms 8104 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 170 ms 7720 KB Output is correct
9 Correct 139 ms 9312 KB Output is correct
10 Correct 151 ms 12328 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 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 42 ms 6708 KB Output is correct
3 Correct 31 ms 5320 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 18 ms 4172 KB Output is correct
6 Correct 60 ms 8104 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 170 ms 7720 KB Output is correct
9 Correct 139 ms 9312 KB Output is correct
10 Correct 151 ms 12328 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 214 ms 12060 KB Output is correct
15 Correct 109 ms 6808 KB Output is correct
16 Correct 151 ms 9508 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 269 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 1 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 66 ms 3500 KB Output is correct
3 Correct 121 ms 4144 KB Output is correct
4 Correct 171 ms 7228 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 66 ms 3500 KB Output is correct
3 Correct 121 ms 4144 KB Output is correct
4 Correct 171 ms 7228 KB Output is correct
5 Partially correct 259 ms 14372 KB Output is partially correct
6 Partially correct 240 ms 14428 KB Output is partially correct
7 Partially correct 248 ms 14424 KB Output is partially correct
8 Partially correct 285 ms 13688 KB Output is partially correct
9 Correct 198 ms 6520 KB Output is correct
10 Correct 257 ms 12148 KB Output is correct
11 Partially correct 282 ms 12540 KB Output is partially correct
12 Partially correct 148 ms 7316 KB Output is partially correct
13 Partially correct 148 ms 8040 KB Output is partially correct
14 Partially correct 154 ms 8088 KB Output is partially correct
15 Partially correct 151 ms 8248 KB Output is partially correct
16 Partially correct 5 ms 588 KB Output is partially correct
17 Partially correct 154 ms 6936 KB Output is partially correct
18 Partially correct 165 ms 6828 KB Output is partially correct
19 Partially correct 184 ms 7628 KB Output is partially correct
20 Partially correct 238 ms 12112 KB Output is partially correct
21 Partially correct 279 ms 11508 KB Output is partially correct
22 Partially correct 221 ms 10676 KB Output is partially correct