oj.uz

Submission #300028

# Submission time Handle Problem Language Result Execution time Memory
300028 2020-09-16T07:06:02 Z square1001 Mechanical Doll (IOI18_doll) C++14
63 / 100
 242 ms 12640 KB 
#include "doll.h"
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
void create_circuit(int M, std::vector<int> A) {
	int N = A.size();
	vector<vector<int> > qs(M + 1);
	for(int i = 0; i < N; ++i) {
		qs[A[i]].push_back(i);
	}
	bool subtask3 = true;
	for(int i = 1; i <= M; ++i) {
		if(qs[i].size() >= 5) {
			subtask3 = false;
		}
	}
	if(subtask3) {
		vector<int> C1(M + 1, 0), X1, Y1;
		A.push_back(0);
		C1[0] = A[0];
		for(int i = 1; i <= M; ++i) {
			if(qs[i].size() == 0) continue;
			int ns = X1.size();
			if(qs[i].size() == 1) {
				C1[i] = A[qs[i][0] + 1];
			}
			if(qs[i].size() == 2) {
				C1[i] = -(ns + 1);
				X1.push_back(A[qs[i][0] + 1]);
				Y1.push_back(A[qs[i][1] + 1]);
			}
			if(qs[i].size() == 3) {
				C1[i] = -(ns + 1);
				X1.push_back(-(ns + 2));
				Y1.push_back(-(ns + 3));
				X1.push_back(-(ns + 1));
				Y1.push_back(A[qs[i][1] + 1]);
				X1.push_back(A[qs[i][0] + 1]);
				Y1.push_back(A[qs[i][2] + 1]);
			}
			if(qs[i].size() == 4) {
				C1[i] = -(ns + 1);
				X1.push_back(-(ns + 2));
				Y1.push_back(-(ns + 3));
				X1.push_back(A[qs[i][0] + 1]);
				Y1.push_back(A[qs[i][2] + 1]);
				X1.push_back(A[qs[i][1] + 1]);
				Y1.push_back(A[qs[i][3] + 1]);
			}
		}
		answer(C1, X1, Y1);
		return;
	}
	int bits = 1;
	while((1 << bits) < N) ++bits;
	vector<int> C(M + 1, -1);
	C[0] = A[0];
	vector<int> X((1 << bits) - 1, -1), Y((1 << bits) - 1, -1);
	for(int i = 1; i < 1 << (bits - 1); ++i) {
		X[i - 1] = -(2 * i);
		Y[i - 1] = -(2 * i + 1);
	}
	vector<int> perm;
	for(int i = 1 << bits; i < 2 << bits; ++i) {
		perm.push_back(i);
	}
	sort(perm.begin(), perm.end(), [&](int i, int j) {
		for(int k = 0; k < bits; ++k) {
			if(((i >> k) & 1) != ((j >> k) & 1)) {
				return ((i >> k) & 1) < ((j >> k) & 1);
			}
		}
		return false;
	});
	for(int i = 0; i < 1 << bits; ++i) {
		int tar = i - ((1 << bits) - N);
		if(tar < 0) tar = -1;
		else if(i != ((1 << bits) - 1)) tar = A[tar + 1];
		else tar = 0;
		if(perm[i] % 2 == 0) {
			X[perm[i] / 2 - 1] = tar;
		}
		else {
			Y[perm[i] / 2 - 1] = tar;
		}
	}
	answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 36 ms 6344 KB Output is correct
3 Correct 28 ms 5076 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 18 ms 3788 KB Output is correct
6 Correct 48 ms 7704 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 36 ms 6344 KB Output is correct
3 Correct 28 ms 5076 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 18 ms 3788 KB Output is correct
6 Correct 48 ms 7704 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 75 ms 7276 KB Output is correct
9 Correct 59 ms 8512 KB Output is correct
10 Correct 113 ms 11288 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 36 ms 6344 KB Output is correct
3 Correct 28 ms 5076 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 18 ms 3788 KB Output is correct
6 Correct 48 ms 7704 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 75 ms 7276 KB Output is correct
9 Correct 59 ms 8512 KB Output is correct
10 Correct 113 ms 11288 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 100 ms 10956 KB Output is correct
15 Correct 56 ms 5928 KB Output is correct
16 Correct 85 ms 8616 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 97 ms 10588 KB Output is correct
21 Correct 2 ms 204 KB Output is correct
22 Correct 2 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 284 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
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 204 KB Output is partially correct
2 Correct 105 ms 5532 KB Output is correct
3 Partially correct 181 ms 9152 KB Output is partially correct
4 Partially correct 204 ms 9916 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 204 KB Output is partially correct
2 Correct 105 ms 5532 KB Output is correct
3 Partially correct 181 ms 9152 KB Output is partially correct
4 Partially correct 204 ms 9916 KB Output is partially correct
5 Partially correct 228 ms 12640 KB Output is partially correct
6 Partially correct 242 ms 11816 KB Output is partially correct
7 Partially correct 218 ms 12088 KB Output is partially correct
8 Partially correct 209 ms 11300 KB Output is partially correct
9 Partially correct 187 ms 9104 KB Output is partially correct
10 Partially correct 202 ms 10680 KB Output is partially correct
11 Partially correct 196 ms 10948 KB Output is partially correct
12 Partially correct 187 ms 9752 KB Output is partially correct
13 Correct 114 ms 6824 KB Output is correct
14 Partially correct 196 ms 10532 KB Output is partially correct
15 Partially correct 215 ms 10936 KB Output is partially correct
16 Partially correct 7 ms 588 KB Output is partially correct
17 Correct 101 ms 5968 KB Output is correct
18 Correct 99 ms 6032 KB Output is correct
19 Partially correct 206 ms 9628 KB Output is partially correct
20 Partially correct 215 ms 10584 KB Output is partially correct
21 Partially correct 197 ms 10688 KB Output is partially correct
22 Partially correct 217 ms 10412 KB Output is partially correct