oj.uz

Submission #75184

# Submission time Handle Problem Language Result Execution time Memory
75184 2018-09-08T16:12:38 Z tmwilliamlin168 Mechanical Doll (IOI18_doll) C++14
100 / 100
 166 ms 10388 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 60 ms 7188 KB Output is correct
3 Correct 54 ms 6796 KB Output is correct
4 Correct 4 ms 4300 KB Output is correct
5 Correct 17 ms 5580 KB Output is correct
6 Correct 83 ms 7980 KB Output is correct
7 Correct 3 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 60 ms 7188 KB Output is correct
3 Correct 54 ms 6796 KB Output is correct
4 Correct 4 ms 4300 KB Output is correct
5 Correct 17 ms 5580 KB Output is correct
6 Correct 83 ms 7980 KB Output is correct
7 Correct 3 ms 4300 KB Output is correct
8 Correct 90 ms 8380 KB Output is correct
9 Correct 107 ms 8764 KB Output is correct
10 Correct 160 ms 10388 KB Output is correct
11 Correct 4 ms 4300 KB Output is correct
12 Correct 5 ms 4300 KB Output is correct
13 Correct 4 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 60 ms 7188 KB Output is correct
3 Correct 54 ms 6796 KB Output is correct
4 Correct 4 ms 4300 KB Output is correct
5 Correct 17 ms 5580 KB Output is correct
6 Correct 83 ms 7980 KB Output is correct
7 Correct 3 ms 4300 KB Output is correct
8 Correct 90 ms 8380 KB Output is correct
9 Correct 107 ms 8764 KB Output is correct
10 Correct 160 ms 10388 KB Output is correct
11 Correct 4 ms 4300 KB Output is correct
12 Correct 5 ms 4300 KB Output is correct
13 Correct 4 ms 4300 KB Output is correct
14 Correct 166 ms 10060 KB Output is correct
15 Correct 102 ms 7996 KB Output is correct
16 Correct 131 ms 9868 KB Output is correct
17 Correct 4 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 132 ms 10136 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 3 ms 4300 KB Output is correct
3 Correct 3 ms 4300 KB Output is correct
4 Correct 3 ms 4300 KB Output is correct
5 Correct 3 ms 4300 KB Output is correct
6 Correct 3 ms 4300 KB Output is correct
7 Correct 4 ms 4300 KB Output is correct
8 Correct 4 ms 4400 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4300 KB Output is correct
2 Correct 78 ms 7616 KB Output is correct
3 Correct 86 ms 7612 KB Output is correct
4 Correct 125 ms 9236 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4300 KB Output is correct
2 Correct 78 ms 7616 KB Output is correct
3 Correct 86 ms 7612 KB Output is correct
4 Correct 125 ms 9236 KB Output is correct
5 Correct 126 ms 9816 KB Output is correct
6 Correct 135 ms 9824 KB Output is correct
7 Correct 138 ms 9960 KB Output is correct
8 Correct 126 ms 9684 KB Output is correct
9 Correct 96 ms 7620 KB Output is correct
10 Correct 125 ms 9504 KB Output is correct
11 Correct 133 ms 9284 KB Output is correct
12 Correct 85 ms 7604 KB Output is correct
13 Correct 82 ms 7864 KB Output is correct
14 Correct 91 ms 8008 KB Output is correct
15 Correct 86 ms 8120 KB Output is correct
16 Correct 6 ms 4432 KB Output is correct
17 Correct 96 ms 7612 KB Output is correct
18 Correct 80 ms 7572 KB Output is correct
19 Correct 82 ms 7620 KB Output is correct
20 Correct 126 ms 9428 KB Output is correct
21 Correct 120 ms 9292 KB Output is correct
22 Correct 124 ms 9284 KB Output is correct