oj.uz

Submission #1043258

# Submission time Handle Problem Language Result Execution time Memory
1043258 2024-08-04T06:45:33 Z yanb Mechanical Doll (IOI18_doll) C++14
82.5995 / 100
 93 ms 20388 KB 
#include <bits/stdc++.h>

using namespace std;
    
//#define int long long
#define pii pair<int, int>

void answer(vector<signed> C, vector<signed> X, vector<signed> Y);

void dfs(vector<int> &X, vector<int> &Y, int v) {
	int u = X[-v - 1];
	if (u < -1) {
		dfs(X, Y, u);
		if (X[-u - 1] == -1 && Y[-u - 1] == -1) X[-v - 1] = -1;
	}
	u = Y[-v - 1];
	if (u < -1) {
		dfs(X, Y, u);
		if (X[-u - 1] == -1 && Y[-u - 1] == -1) Y[-v - 1] = -1;
	}
}

void create_circuit6(int k, vector<int> a) {
	a.push_back(0);
	int n = a.size();

	vector<int> C(k + 1, -1), X, Y;

	int cnt = n;
	int z = 1, ord = 0;
	while (z < cnt) {
		z *= 2;
		ord++;
	}
	ord = max(1, ord);

	vector<int> p(z);
	p[0] = 0;
	for (int i = 0; i < ord; i++) {
		for (int ni = 0; ni < (1 << i); ni++) {
			p[(1 << i) + ni] = p[ni] + (1 << (ord - i - 1));
		}
	}

	for (int i = 0; i < z - n; i++) p[i] = -1;
	vector<pii> mp(z);
	for (int i = 0; i < z; i++) mp[i] = {p[i], i};
	sort(mp.begin(), mp.end());
	for (int i = z - n; i < z; i++) {
		p[mp[i].second] = i - z + n;
	}

	vector<int> v(z);
	for (int i = 0; i < z; i++) {
		v[i] = (p[i] == -1 ? -1 : a[p[i]]);
	}

	vector<int> X_(z), Y_(z);
	for (int ni = 1; ni < z / 2; ni++) {
		X_[ni] = -ni * 2 - 1;
		Y_[ni] = -ni * 2;
	}
	for (int ni = 0; ni < z / 2; ni++) {
		X_[z - ni - 1] = v[ni * 2];
		Y_[z - ni - 1] = v[ni * 2 + 1];
	}

	for (int i = 1; i < z; i++) {
		X.push_back(X_[i]);
		Y.push_back(Y_[i]);
	}

	dfs(X, Y, -1);

	/*for (int x : X) cout << x << " ";
	cout << "\n";
	for (int x : Y) cout << x << " ";
	cout << "\n\n";*/

	vector<int> Xf, Yf, f(z);
	int tm = -1;
	for (int i = 0; i < z - 1; i++) {
		if (X[i] == -1 && Y[i] == -1) continue;
		f[i] = tm;
		tm--;
	}

	/*for (int i = 0; i < z; i++) {
		cout << f[i] << " ";
	}
	cout << "\n\n";*/

	for (int i = 0; i < z; i++) {
		if (X[i] == -1 && Y[i] == -1) continue;
		Xf.push_back(X[i] < 0 ? f[-X[i] - 1] : X[i]);
		Yf.push_back(Y[i] < 0 ? f[-Y[i] - 1] : Y[i]);
	}

	/*for (int x : Xf) cout << x << " ";
	cout << "\n";
	for (int x : Yf) cout << x << " ";
	cout << "\n";*/

	answer(C, Xf, Yf);
}

void create_circuit3(int k, vector<int> a) {
	int n = a.size();
	a.push_back(0);
	vector<vector<int>> g(k + 1);
	g[0].push_back(a[0]);
	for (int i = 0; i < n; i++) {
		g[a[i]].push_back(a[i + 1]);
	}
 
	vector<int> C(k + 1), X, Y;
	C[0] = g[0][0];
	for (int j = 1; j < k + 1; j++) {
		int cnt = g[j].size();
		int z = 1, ord = 0;
		while (z < cnt) {
			z *= 2;
			ord++;
		}
 
		if (ord == 0) {
			if (cnt == 1) C[j] = g[j][0];
			continue;
		}
 
		vector<int> p(z);
		p[0] = 0;
		for (int i = 0; i < ord; i++) {
			for (int ni = 0; ni < (1 << i); ni++) {
				p[(1 << i) + ni] = p[ni] + (1 << (ord - i - 1));
			}
		}
 
		int wnots = X.size();
		C[j] = -wnots - 1;
 
		vector<int> v(z, -wnots - 1);
		for (int i = z - (int) g[j].size(); i < z; i++) {
			v[i] = g[j][i - z + (int) g[j].size()];
		}
 
		vector<int> vp(z);
		for (int i = 0; i < z; i++) {
			vp[p[i]] = v[i];
		}
 
		vector<int> X_(z), Y_(z);
		for (int ni = 1; ni < z / 2; ni++) {
			X_[ni] = -ni * 2 - wnots;
			Y_[ni] = -ni * 2 - 1 - wnots;
		}
		for (int ni = 0; ni < z / 2; ni++) {
			X_[ni + z / 2] = vp[ni * 2];
			Y_[ni + z / 2] = vp[ni * 2 + 1];
		}
 
		for (int i = 1; i < z; i++) {
			X.push_back(X_[i]);
			Y.push_back(Y_[i]);
		}
	}
 
	answer(C, X, Y);
}

void create_circuit(int k, vector<int> a) {
	map<int, int> freq;
	for (int x : a) {
		freq[x]++;
	}

	for (auto [_, cnt] : freq) {
		if (cnt > 4) {
			create_circuit6(k, a);
			return;
		}
	}

	create_circuit3(k, a);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:177:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  177 |  for (auto [_, cnt] : freq) {
      |            ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 30 ms 10060 KB Output is correct
3 Correct 30 ms 8932 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 3932 KB Output is correct
6 Correct 47 ms 13476 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 30 ms 10060 KB Output is correct
3 Correct 30 ms 8932 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 3932 KB Output is correct
6 Correct 47 ms 13476 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 54 ms 11856 KB Output is correct
9 Correct 63 ms 14108 KB Output is correct
10 Correct 87 ms 18240 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 30 ms 10060 KB Output is correct
3 Correct 30 ms 8932 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 3932 KB Output is correct
6 Correct 47 ms 13476 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 54 ms 11856 KB Output is correct
9 Correct 63 ms 14108 KB Output is correct
10 Correct 87 ms 18240 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 93 ms 16300 KB Output is correct
15 Correct 46 ms 9052 KB Output is correct
16 Correct 75 ms 13380 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 388 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 85 ms 16544 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
16.1998901226 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Partially correct 40 ms 15140 KB Output is partially correct
3 Correct 34 ms 15280 KB Output is correct
4 Correct 48 ms 17988 KB Output is correct

Subtask #6
50.3996581592 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Partially correct 40 ms 15140 KB Output is partially correct
3 Correct 34 ms 15280 KB Output is correct
4 Correct 48 ms 17988 KB Output is correct
5 Correct 85 ms 20388 KB Output is correct
6 Correct 76 ms 19268 KB Output is correct
7 Correct 80 ms 19784 KB Output is correct
8 Correct 66 ms 18680 KB Output is correct
9 Correct 38 ms 15276 KB Output is correct
10 Correct 58 ms 18484 KB Output is correct
11 Correct 56 ms 18240 KB Output is correct
12 Correct 41 ms 15280 KB Output is correct
13 Partially correct 48 ms 16040 KB Output is partially correct
14 Correct 50 ms 16292 KB Output is correct
15 Correct 53 ms 16548 KB Output is correct
16 Correct 2 ms 856 KB Output is correct
17 Correct 36 ms 10896 KB Output is correct
18 Partially correct 38 ms 15276 KB Output is partially correct
19 Correct 41 ms 15264 KB Output is correct
20 Correct 61 ms 18460 KB Output is correct
21 Correct 59 ms 18216 KB Output is correct
22 Correct 59 ms 18240 KB Output is correct