oj.uz

Submission #295129

# Submission time Handle Problem Language Result Execution time Memory
295129 2020-09-09T13:39:33 Z Saboon Mechanical Doll (IOI18_doll) C++17
100 / 100
 194 ms 8152 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 10;
const int inf = 1e8;
vector<int> X,Y;
bool mark[maxn];
int n, Sz, newint = 1;

int build(int L, int R, int x){
	if (L+1 == R)
		return inf;
	int id = newint ++;
	X.push_back(1), Y.push_back(1);
	int mid = (L+R) >> 1;
	if (x < mid)
		X[id-1] = build(L, mid, x);
	Y[id-1] = build(mid, R, x);
	return id;
}

int assign(int id, int L, int R, int x){
	if (id == 1)
		L = 0, R = Sz;
	if (L+1 == R)
		return -x;
	int mid = (L + R) >> 1;
	if (mark[id-1] == 0){
		mark[id-1] ^= 1;
		X[id-1] = assign(X[id-1], L, mid, x);
	}
	else{
		mark[id-1] ^= 1;
		Y[id-1] = assign(Y[id-1], mid, R, x);
	}
	return id;
}

void create_circuit(int m, vector<int> A){
	n = A.size();
	Sz = n+1;
	while (__builtin_popcount(Sz) != 1)
		Sz ++;
	vector<int> C(m+1);
	for (int i = 0; i < m+1; i++)
		C[i] = -1;
	build (0, Sz,Sz-n-1);
	for (int i = 0; i < n; i++)
		assign(1, 0, Sz, A[i]);
	assign(1, 0, Sz, 0);
	for (int i = 1; i < newint; i++)
		X[i-1] *= -1, Y[i-1] *= -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 60 ms 3664 KB Output is correct
3 Correct 57 ms 3612 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 17 ms 1356 KB Output is correct
6 Correct 79 ms 4868 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 60 ms 3664 KB Output is correct
3 Correct 57 ms 3612 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 17 ms 1356 KB Output is correct
6 Correct 79 ms 4868 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 107 ms 6420 KB Output is correct
9 Correct 112 ms 6772 KB Output is correct
10 Correct 165 ms 8152 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 60 ms 3664 KB Output is correct
3 Correct 57 ms 3612 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 17 ms 1356 KB Output is correct
6 Correct 79 ms 4868 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 107 ms 6420 KB Output is correct
9 Correct 112 ms 6772 KB Output is correct
10 Correct 165 ms 8152 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 153 ms 7792 KB Output is correct
15 Correct 106 ms 6056 KB Output is correct
16 Correct 168 ms 7500 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 165 ms 7932 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 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 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 107 ms 5228 KB Output is correct
3 Correct 124 ms 5136 KB Output is correct
4 Correct 162 ms 6912 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 107 ms 5228 KB Output is correct
3 Correct 124 ms 5136 KB Output is correct
4 Correct 162 ms 6912 KB Output is correct
5 Correct 169 ms 7384 KB Output is correct
6 Correct 165 ms 7296 KB Output is correct
7 Correct 163 ms 7360 KB Output is correct
8 Correct 194 ms 7160 KB Output is correct
9 Correct 94 ms 5144 KB Output is correct
10 Correct 146 ms 7080 KB Output is correct
11 Correct 161 ms 6872 KB Output is correct
12 Correct 102 ms 5432 KB Output is correct
13 Correct 101 ms 5912 KB Output is correct
14 Correct 116 ms 5920 KB Output is correct
15 Correct 114 ms 6008 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 93 ms 4668 KB Output is correct
18 Correct 99 ms 5400 KB Output is correct
19 Correct 102 ms 5440 KB Output is correct
20 Correct 145 ms 6936 KB Output is correct
21 Correct 152 ms 6972 KB Output is correct
22 Correct 153 ms 6828 KB Output is correct