oj.uz

Submission #158058

# Submission time Handle Problem Language Result Execution time Memory
158058 2019-10-14T14:30:44 Z kig9981 Mechanical Doll (IOI18_doll) C++17
100 / 100
 150 ms 10460 KB 
#include "doll.h"
#include <bits/stdc++.h>
 
using namespace std;

int tree[1<<19];
 
void create_circuit(int M, vector<int> A)
{
	int N=A.size()+1, c=-1, SZ=1;
	vector<int> C(M+1,-1), X(1), Y(1), temp;
	A.push_back(0);
	for(;SZ<N;SZ<<=1);
	memset(tree,0x7f,sizeof(tree));
	for(int i=0;i<N;i++) {
		int j=0;
		for(int b=1;b<SZ;b<<=1) {
			j<<=1;
			if((SZ-1-i)&b) j|=1;
		}
		temp.push_back(j);
	}
	sort(temp.begin(),temp.end());
	for(int i=0;i<N;i++) {
		int j=0;
		for(int b=1;b<SZ;b<<=1) {
			j<<=1;
			if(temp[i]&b) j|=1;
		}
		tree[SZ+j]=A[i];
	}
	for(int i=SZ;--i>1;) if(tree[2*i]!=0x7f7f7f7f || tree[2*i+1]!=0x7f7f7f7f) {
		tree[i]=--c;
		X.push_back(tree[2*i]==0x7f7f7f7f ? -1:tree[2*i]);
		Y.push_back(tree[2*i+1]==0x7f7f7f7f ? -1:tree[2*i+1]);
	}
	tree[1]=-1;
	X[0]=tree[2]==0x7f7f7f7f ? -1:tree[2];
	Y[0]=tree[3]==0x7f7f7f7f ? -1:tree[3];
	answer(C,X,Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2252 KB Output is correct
2 Correct 43 ms 6092 KB Output is correct
3 Correct 41 ms 5704 KB Output is correct
4 Correct 3 ms 2252 KB Output is correct
5 Correct 15 ms 3404 KB Output is correct
6 Correct 60 ms 7156 KB Output is correct
7 Correct 3 ms 2252 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2252 KB Output is correct
2 Correct 43 ms 6092 KB Output is correct
3 Correct 41 ms 5704 KB Output is correct
4 Correct 3 ms 2252 KB Output is correct
5 Correct 15 ms 3404 KB Output is correct
6 Correct 60 ms 7156 KB Output is correct
7 Correct 3 ms 2252 KB Output is correct
8 Correct 89 ms 7648 KB Output is correct
9 Correct 76 ms 8060 KB Output is correct
10 Correct 109 ms 10460 KB Output is correct
11 Correct 2 ms 2252 KB Output is correct
12 Correct 2 ms 2252 KB Output is correct
13 Correct 2 ms 2252 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2252 KB Output is correct
2 Correct 43 ms 6092 KB Output is correct
3 Correct 41 ms 5704 KB Output is correct
4 Correct 3 ms 2252 KB Output is correct
5 Correct 15 ms 3404 KB Output is correct
6 Correct 60 ms 7156 KB Output is correct
7 Correct 3 ms 2252 KB Output is correct
8 Correct 89 ms 7648 KB Output is correct
9 Correct 76 ms 8060 KB Output is correct
10 Correct 109 ms 10460 KB Output is correct
11 Correct 2 ms 2252 KB Output is correct
12 Correct 2 ms 2252 KB Output is correct
13 Correct 2 ms 2252 KB Output is correct
14 Correct 102 ms 10144 KB Output is correct
15 Correct 68 ms 7256 KB Output is correct
16 Correct 150 ms 9908 KB Output is correct
17 Correct 2 ms 2252 KB Output is correct
18 Correct 2 ms 2252 KB Output is correct
19 Correct 3 ms 2252 KB Output is correct
20 Correct 103 ms 10284 KB Output is correct
21 Correct 3 ms 2252 KB Output is correct
22 Correct 3 ms 2252 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2252 KB Output is correct
2 Correct 62 ms 6856 KB Output is correct
3 Correct 61 ms 6876 KB Output is correct
4 Correct 97 ms 9304 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2252 KB Output is correct
2 Correct 62 ms 6856 KB Output is correct
3 Correct 61 ms 6876 KB Output is correct
4 Correct 97 ms 9304 KB Output is correct
5 Correct 105 ms 9780 KB Output is correct
6 Correct 96 ms 9676 KB Output is correct
7 Correct 99 ms 9652 KB Output is correct
8 Correct 99 ms 9484 KB Output is correct
9 Correct 60 ms 6860 KB Output is correct
10 Correct 111 ms 9388 KB Output is correct
11 Correct 113 ms 9384 KB Output is correct
12 Correct 61 ms 6868 KB Output is correct
13 Correct 65 ms 7152 KB Output is correct
14 Correct 66 ms 7128 KB Output is correct
15 Correct 68 ms 7276 KB Output is correct
16 Correct 4 ms 2508 KB Output is correct
17 Correct 60 ms 8616 KB Output is correct
18 Correct 64 ms 6896 KB Output is correct
19 Correct 69 ms 6900 KB Output is correct
20 Correct 103 ms 9420 KB Output is correct
21 Correct 103 ms 9368 KB Output is correct
22 Correct 133 ms 9396 KB Output is correct