oj.uz

Submission #604920

# Submission time Handle Problem Language Result Execution time Memory
604920 2022-07-25T10:50:57 Z DanShaders Mechanical Doll (IOI18_doll) C++17
70.6719 / 100
 128 ms 11716 KB 
//Dgrader.cpp
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
using ll = long long;
using ld = long double;

const int N = 4e5 + 10;

pair<int, int> switches[N];
int next_free = 1;

int create(vector<int> a) {
	int result = next_free++;
	if (sz(a) == 1) {
		switches[result] = {-result, a[0]};
	} else if (sz(a) == 2) {
		switches[result] = {a[0], a[1]};
	} else {
		vector<int> left, right;
		for (int i = 0; i < sz(a); ++i) {
			(i % 2 ? right : left).push_back(a[i]);
		}
		switches[result] = {
			(count(all(left), -1) == sz(left)) ? -1 : -create(left),
			(count(all(right), -1) == sz(right)) ? -1 : -create(right)
		};
	}
	return result;
}

void create_circuit(int m, vector<int> a) {
	a.push_back(0);
	int nsize = sz(a);
	while (nsize & (nsize - 1)) {
		++nsize;
	}
	vector<int> usable(nsize, -1);
	int n = __builtin_ctz(nsize);
	for (int i = 0; i < sz(a) - 1; ++i) {
		int where = 0;
		for (int j = 0; j < n; ++j) {
			where |= (i >> j & 1) << (n - j - 1);
		}
		usable[where] = 0;
	}
	usable.back() = 0;
	for (int i = 0, it = 0; i < nsize; ++i) {
		if (usable[i] == 0) {
			usable[i] = a[it++];
		}
	}
	// for (int u : usable) {
	// 	cout << u << " ";
	// }
	// cout << endl;
	create(usable);
	vector<int> xs, ys;
	for (int i = 1; i < next_free; ++i) {
		xs.push_back(switches[i].x);
		ys.push_back(switches[i].y);

	}
	answer(vector<int>(m + 1, -1), xs, ys);
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 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 212 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 212 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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #5
14.7580402392 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Correct 64 ms 8008 KB Output is correct
3 Partially correct 73 ms 8200 KB Output is partially correct
4 Partially correct 95 ms 10876 KB Output is partially correct

Subtask #6
45.9139029664 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Correct 64 ms 8008 KB Output is correct
3 Partially correct 73 ms 8200 KB Output is partially correct
4 Partially correct 95 ms 10876 KB Output is partially correct
5 Partially correct 104 ms 11716 KB Output is partially correct
6 Partially correct 128 ms 11580 KB Output is partially correct
7 Partially correct 108 ms 11576 KB Output is partially correct
8 Partially correct 117 ms 11544 KB Output is partially correct
9 Partially correct 65 ms 8188 KB Output is partially correct
10 Partially correct 110 ms 11456 KB Output is partially correct
11 Partially correct 99 ms 11192 KB Output is partially correct
12 Partially correct 67 ms 8168 KB Output is partially correct
13 Correct 80 ms 8124 KB Output is correct
14 Partially correct 71 ms 8316 KB Output is partially correct
15 Partially correct 68 ms 8472 KB Output is partially correct
16 Partially correct 2 ms 596 KB Output is partially correct
17 Correct 65 ms 7828 KB Output is correct
18 Correct 87 ms 7980 KB Output is correct
19 Partially correct 67 ms 8236 KB Output is partially correct
20 Partially correct 99 ms 11412 KB Output is partially correct
21 Partially correct 103 ms 11152 KB Output is partially correct
22 Partially correct 98 ms 11156 KB Output is partially correct