oj.uz

Submission #292164

# Submission time Handle Problem Language Result Execution time Memory
292164 2020-09-06T13:11:46 Z Namnamseo Mechanical Doll (IOI18_doll) C++17
100 / 100
 105 ms 10308 KB 
#include "doll.h"
#include <cassert>
#include <cstdio>
#include <algorithm>
using namespace std;
#define pb push_back

int nn;

const int maxn = int(4e5) + 10;
int x[maxn];
int y[maxn];
int c[maxn];

int f(int b, vector<int>& a)
{
	if (b == 0) return a[0];

	for(int i=0, j=0; i<(1<<b); ++i) {
		if (i<j) swap(a[i], a[j]);
		int t = (1<<(b-1));
		while (j&t) j^=t, t>>=1;
		j|=t;
	}
	int m = 1<<(b-1);
	int r = nn+1;
	assert(int(a.size()) == m*2);
	for(int i=1; i<m; ++i) x[nn+i]=-(nn+2*i), y[nn+i]=-(nn+2*i+1);
	for(int i=m, p=0; i<2*m; ++i) x[nn+i]=a[p++], y[nn+i]=a[p++];
	nn += 2*m-1;
	return -r;
}

void create_circuit(int M, vector<int> A) {
	int N = A.size();
	vector<int> bits;
	for(int i=0; i<30; ++i) if (1&(N>>i)) bits.pb(i);
	int mb = bits.back() + 1;

	vector<vector<int>> as(30);
	{ int pt = 0; for(int i=1; i<(1<<mb); ++i) {
		int j = (i&(-i));
		j = mb-1-__builtin_ctz(j);
		if (N&(1<<j)) {
			as[mb-1-j].pb(A[pt++]);
		}
	} }

	nn = mb;
	for(int i=0; i<mb; ++i) x[i+1] = -1, y[i+1] = -(i+2);
	y[mb] = 0;
	for(int b:bits) {
		x[mb-b] = f(b, as[mb-1-b]);
	}

	vector<int> C(M+1, -1);
	vector<int> X(x+1, x+nn+1);
	vector<int> Y(y+1, y+nn+1);

	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 35 ms 4424 KB Output is correct
3 Correct 31 ms 4040 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 17 ms 1356 KB Output is correct
6 Correct 78 ms 5800 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 35 ms 4424 KB Output is correct
3 Correct 31 ms 4040 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 17 ms 1356 KB Output is correct
6 Correct 78 ms 5800 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 76 ms 6668 KB Output is correct
9 Correct 57 ms 7236 KB Output is correct
10 Correct 85 ms 10308 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 35 ms 4424 KB Output is correct
3 Correct 31 ms 4040 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 17 ms 1356 KB Output is correct
6 Correct 78 ms 5800 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 76 ms 6668 KB Output is correct
9 Correct 57 ms 7236 KB Output is correct
10 Correct 85 ms 10308 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 89 ms 9900 KB Output is correct
15 Correct 51 ms 6316 KB Output is correct
16 Correct 83 ms 9480 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 93 ms 10028 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 1 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 49 ms 6044 KB Output is correct
3 Correct 58 ms 6068 KB Output is correct
4 Correct 80 ms 9136 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 49 ms 6044 KB Output is correct
3 Correct 58 ms 6068 KB Output is correct
4 Correct 80 ms 9136 KB Output is correct
5 Correct 85 ms 9384 KB Output is correct
6 Correct 105 ms 9284 KB Output is correct
7 Correct 75 ms 9252 KB Output is correct
8 Correct 71 ms 9132 KB Output is correct
9 Correct 47 ms 6076 KB Output is correct
10 Correct 76 ms 9128 KB Output is correct
11 Correct 74 ms 9148 KB Output is correct
12 Correct 64 ms 6044 KB Output is correct
13 Correct 49 ms 6048 KB Output is correct
14 Correct 50 ms 6180 KB Output is correct
15 Correct 59 ms 6212 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 53 ms 5976 KB Output is correct
18 Correct 52 ms 6056 KB Output is correct
19 Correct 55 ms 6044 KB Output is correct
20 Correct 73 ms 9128 KB Output is correct
21 Correct 81 ms 9128 KB Output is correct
22 Correct 75 ms 9124 KB Output is correct