oj.uz

Submission #238336

# Submission time Handle Problem Language Result Execution time Memory
238336 2020-06-10T20:01:00 Z Jatana Mechanical Doll (IOI18_doll) C++17
66.6074 / 100
 259 ms 10176 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);
}
vector<int> gen(int k) {
	if (k == 0) return {0};
	vector<int> sub = gen(k - 1);
	vector<int> real;
	for (int i = 0; i < le(sub); i++) {
		real.pb(sub[i]);
		real.pb(sub[i] + (1 << (k - 1)));
	}
	return real;
}
vector<int> inv(vector<int> p) {
	vector<int> q(le(p));
	for (int i = 0; i < le(p); i++) {
		q[p[i]] = i;
	}
	return q;
}
 
mt19937 rng(1337);
void create_circuit(int M, vector<int> A) {
	X.clear(); Y.clear();
	int N = A.size();
	A.pb(0);
	int sz = le(A);
	inc = 0;
	int root = go(sz);
	int wait = inc;
	reverse(A.begin(), A.end());
	vector<int> C(M + 1, root);
	C[0] = root;
	int cur = root;
	int real = -1;
	while (cur) {
		// cerr << cur << " ";
		if (cur > 0) {
			real = cur;
			cur = C[cur];
		}	else {
			cur = (-cur) - 1;
			if (X[cur] == -1e9) {
				bool cond = (1 + wait + le(A)) % 2;
				// bool cond = binary_search(order[real].begin(), order[real].end(), it[real]);
				if (wait
						&& ((le(A) == 1) || cond)) {
					wait--;
					X[cur] = root;
				} else {
					// cout << "decide" << endl;
					X[cur] = A.back();
					A.pop_back();
				}
			}
			swap(X[cur], Y[cur]);
			cur = Y[cur];
		}
	}
	// cerr << endl;
	// return;
	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;
				}
			}
		}
		if (it == 0) {
			int killed = 0;
			for (int x : del) killed++;
			// cout << "killed: " << killed << endl;
		}
	}
	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:115:13: warning: unused variable 'x' [-Wunused-variable]
  115 |    for (int x : del) killed++;
      |             ^
doll.cpp:48:6: warning: unused variable 'N' [-Wunused-variable]
   48 |  int N = A.size();
      |      ^
doll.cpp:58:6: warning: variable 'real' set but not used [-Wunused-but-set-variable]
   58 |  int real = -1;
      |      ^~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

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 2 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 100 ms 3648 KB Output is correct
3 Correct 97 ms 3656 KB Output is correct
4 Correct 165 ms 6812 KB Output is correct

Subtask #6
38.6073639 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 100 ms 3648 KB Output is correct
3 Correct 97 ms 3656 KB Output is correct
4 Correct 165 ms 6812 KB Output is correct
5 Partially correct 246 ms 10176 KB Output is partially correct
6 Partially correct 241 ms 9872 KB Output is partially correct
7 Partially correct 237 ms 9868 KB Output is partially correct
8 Partially correct 246 ms 9752 KB Output is partially correct
9 Correct 195 ms 5708 KB Output is correct
10 Partially correct 250 ms 9420 KB Output is partially correct
11 Partially correct 238 ms 9496 KB Output is partially correct
12 Correct 182 ms 7352 KB Output is correct
13 Correct 174 ms 6724 KB Output is correct
14 Partially correct 173 ms 6828 KB Output is partially correct
15 Partially correct 178 ms 6956 KB Output is partially correct
16 Correct 7 ms 512 KB Output is correct
17 Correct 156 ms 6412 KB Output is correct
18 Correct 200 ms 7304 KB Output is correct
19 Correct 165 ms 7376 KB Output is correct
20 Partially correct 235 ms 9628 KB Output is partially correct
21 Partially correct 241 ms 9384 KB Output is partially correct
22 Partially correct 259 ms 9416 KB Output is partially correct