oj.uz

Submission #753957

# Submission time Handle Problem Language Result Execution time Memory
753957 2023-06-06T11:33:52 Z valerikk Mechanical Doll (IOI18_doll) C++17
100 / 100
 158 ms 19924 KB 
#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

namespace {

const int N = 6e5 + 501;

int n, m;
int pw;
vector<int> a;
int n1;
int x[N], y[N];
vector<int> kek;
int pos[N], f[N];
int fuck[N];

int dfs(int v) {
	if (n1 == 0) {
		return 1;
	}
	kek.push_back(v);
	if (v < (1 << pw)) {
		y[v] = dfs(2 * v + 1);
		x[v] = dfs(2 * v);
	} else {
		--n1;
	}
	return v;
}

}

void create_circuit(int m1, vector<int> a1) {
	m = m1;
	a = a1;
	n = a.size() + 1;
	a.push_back(0);
	pw = 0;
	while ((1 << pw) < n) {
		++pw;
	}
	vector<int> ord;
	{
		int v = 1;
		while ((int)ord.size() < (1 << pw)) {
			if (v >= (1 << pw)) {
				ord.push_back(v);
				v = 1;
			} else {
				f[v] ^= 1;
				if (f[v]) {
					v = 2 * v;
				} else {
					v = 2 * v + 1;
				}
			}
		}
	}
	assert((int)ord.size() == (1 << pw));
	for (int i = 0; i < (1 << pw); ++i) {
		pos[ord[i]] = i;
	}
	n1 = n;
	dfs(1);
	vector<int> lol, rofl;
	for (int v : kek) {
		if (v < (1 << pw)) {
			lol.push_back(v);
		} else {
			rofl.push_back(v);
		}
	}
	assert((int)rofl.size() == n);
	sort(rofl.begin(), rofl.end(), [&](int v, int u) {
		return pos[v] < pos[u];
	});
	// for (int v : rofl) {
	// 	cout << v << " ";
	// }
	// cout << endl;
	// for (int i = 0; i < n; ++i) {
	// 	cout << a[i] << " ";
	// }
	// cout << endl;
	for (int i = 0; i < n; ++i) {
		fuck[rofl[i]] = a[i];
	}
	vector<int> c(m + 1, -1);
	sort(lol.begin(), lol.end());
	int s = lol.size();
	vector<int> x1(s), y1(s);
	for (int i = 0; i < s; ++i) {
		int v = lol[i];
		// if (i == 3) {
		// 	cout << v << " " << x[v] << " " << y[v] << endl;
		// 	cout << fuck[x[v]] << " " << fuck[y[v]] << endl;
		// }
		if (x[v] >= (1 << pw)) {
			x1[i] = fuck[x[v]];
		} else {
			x1[i] = lower_bound(lol.begin(), lol.end(), x[v]) - lol.begin();
			x1[i] = -(x1[i] + 1);
		}
		if (y[v] >= (1 << pw)) {
			y1[i] = fuck[y[v]];
		} else {
			y1[i] = lower_bound(lol.begin(), lol.end(), y[v]) - lol.begin();
			y1[i] = -(y1[i] + 1);
		}
	}
	answer(c, x1, y1);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 59 ms 7876 KB Output is correct
3 Correct 62 ms 7376 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 10 ms 1492 KB Output is correct
6 Correct 72 ms 10420 KB Output is correct
7 Correct 0 ms 340 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 59 ms 7876 KB Output is correct
3 Correct 62 ms 7376 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 10 ms 1492 KB Output is correct
6 Correct 72 ms 10420 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 101 ms 12832 KB Output is correct
9 Correct 119 ms 14352 KB Output is correct
10 Correct 158 ms 19924 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 316 KB Output is correct
13 Correct 1 ms 340 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 59 ms 7876 KB Output is correct
3 Correct 62 ms 7376 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 10 ms 1492 KB Output is correct
6 Correct 72 ms 10420 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 101 ms 12832 KB Output is correct
9 Correct 119 ms 14352 KB Output is correct
10 Correct 158 ms 19924 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 316 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 151 ms 19328 KB Output is correct
15 Correct 109 ms 13292 KB Output is correct
16 Correct 137 ms 19216 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 143 ms 19728 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 98 ms 12000 KB Output is correct
3 Correct 108 ms 13024 KB Output is correct
4 Correct 130 ms 18128 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 98 ms 12000 KB Output is correct
3 Correct 108 ms 13024 KB Output is correct
4 Correct 130 ms 18128 KB Output is correct
5 Correct 139 ms 18940 KB Output is correct
6 Correct 153 ms 18980 KB Output is correct
7 Correct 144 ms 18900 KB Output is correct
8 Correct 141 ms 18700 KB Output is correct
9 Correct 102 ms 12976 KB Output is correct
10 Correct 149 ms 18700 KB Output is correct
11 Correct 142 ms 18400 KB Output is correct
12 Correct 107 ms 12892 KB Output is correct
13 Correct 99 ms 13064 KB Output is correct
14 Correct 101 ms 13080 KB Output is correct
15 Correct 111 ms 13108 KB Output is correct
16 Correct 3 ms 712 KB Output is correct
17 Correct 78 ms 12704 KB Output is correct
18 Correct 102 ms 13004 KB Output is correct
19 Correct 93 ms 12972 KB Output is correct
20 Correct 150 ms 18644 KB Output is correct
21 Correct 137 ms 18448 KB Output is correct
22 Correct 138 ms 18496 KB Output is correct