oj.uz

Submission #147103

# Submission time Handle Problem Language Result Execution time Memory
147103 2019-08-27T13:56:17 Z dolphingarlic Mechanical Doll (IOI18_doll) C++14
100 / 100
 149 ms 10444 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

int n, p=1, sti=1;
vector<int> x(1<<19), y(1<<19);
bool b[1<<19];

int bld(int l, int r) {
	if(l>=r)
		return 0;
	if(r<p-n)
		return -1;
	int ts=sti++, m=(l+r)/2;
	x[ts-1]=bld(l, m);
	y[ts-1]=bld(m+1, r);
	return -ts;
}

void pt(int i, int j) {
	int &a=b[-i]?y[-i-1]:x[-i-1];
	b[-i]=!b[-i];
	if(!a)
		a=j;
	else
		pt(a, j);
}

void create_circuit(int m, vector<int> a) {
	n=a.size();
	while(p<n)
		p*=2;
	bld(0, p-1);
	for(int i=1; i<n; ++i)
		pt(-1, a[i]);
	if(n&1)
		pt(-1, -1);
	pt(-1, 0);
	vector<int> c(m+1, -1);
	c[0]=a[0];
	x.resize(sti);
	y.resize(sti);
	answer(c, x, y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4300 KB Output is correct
2 Correct 49 ms 7108 KB Output is correct
3 Correct 47 ms 6784 KB Output is correct
4 Correct 4 ms 4300 KB Output is correct
5 Correct 14 ms 5580 KB Output is correct
6 Correct 70 ms 8004 KB Output is correct
7 Correct 4 ms 4300 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4300 KB Output is correct
2 Correct 49 ms 7108 KB Output is correct
3 Correct 47 ms 6784 KB Output is correct
4 Correct 4 ms 4300 KB Output is correct
5 Correct 14 ms 5580 KB Output is correct
6 Correct 70 ms 8004 KB Output is correct
7 Correct 4 ms 4300 KB Output is correct
8 Correct 88 ms 8372 KB Output is correct
9 Correct 122 ms 8768 KB Output is correct
10 Correct 132 ms 10444 KB Output is correct
11 Correct 3 ms 4300 KB Output is correct
12 Correct 3 ms 4300 KB Output is correct
13 Correct 3 ms 4300 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4300 KB Output is correct
2 Correct 49 ms 7108 KB Output is correct
3 Correct 47 ms 6784 KB Output is correct
4 Correct 4 ms 4300 KB Output is correct
5 Correct 14 ms 5580 KB Output is correct
6 Correct 70 ms 8004 KB Output is correct
7 Correct 4 ms 4300 KB Output is correct
8 Correct 88 ms 8372 KB Output is correct
9 Correct 122 ms 8768 KB Output is correct
10 Correct 132 ms 10444 KB Output is correct
11 Correct 3 ms 4300 KB Output is correct
12 Correct 3 ms 4300 KB Output is correct
13 Correct 3 ms 4300 KB Output is correct
14 Correct 144 ms 10088 KB Output is correct
15 Correct 86 ms 8004 KB Output is correct
16 Correct 149 ms 9948 KB Output is correct
17 Correct 3 ms 4300 KB Output is correct
18 Correct 4 ms 4300 KB Output is correct
19 Correct 3 ms 4300 KB Output is correct
20 Correct 131 ms 10148 KB Output is correct
21 Correct 3 ms 4300 KB Output is correct
22 Correct 3 ms 4300 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4300 KB Output is correct
2 Correct 4 ms 4300 KB Output is correct
3 Correct 4 ms 4300 KB Output is correct
4 Correct 3 ms 4300 KB Output is correct
5 Correct 4 ms 4300 KB Output is correct
6 Correct 3 ms 4300 KB Output is correct
7 Correct 3 ms 4384 KB Output is correct
8 Correct 4 ms 4300 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4300 KB Output is correct
2 Correct 82 ms 7608 KB Output is correct
3 Correct 83 ms 7620 KB Output is correct
4 Correct 126 ms 9240 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4300 KB Output is correct
2 Correct 82 ms 7608 KB Output is correct
3 Correct 83 ms 7620 KB Output is correct
4 Correct 126 ms 9240 KB Output is correct
5 Correct 128 ms 9804 KB Output is correct
6 Correct 133 ms 9832 KB Output is correct
7 Correct 126 ms 9884 KB Output is correct
8 Correct 127 ms 9572 KB Output is correct
9 Correct 81 ms 7604 KB Output is correct
10 Correct 124 ms 9492 KB Output is correct
11 Correct 125 ms 9288 KB Output is correct
12 Correct 88 ms 7616 KB Output is correct
13 Correct 84 ms 7844 KB Output is correct
14 Correct 85 ms 8112 KB Output is correct
15 Correct 88 ms 8080 KB Output is correct
16 Correct 5 ms 4428 KB Output is correct
17 Correct 98 ms 7608 KB Output is correct
18 Correct 83 ms 7612 KB Output is correct
19 Correct 95 ms 7608 KB Output is correct
20 Correct 133 ms 9420 KB Output is correct
21 Correct 147 ms 9240 KB Output is correct
22 Correct 128 ms 9236 KB Output is correct