oj.uz

Submission #120564

# Submission time Handle Problem Language Result Execution time Memory
120564 2019-06-25T00:46:55 Z imyujin Mechanical Doll (IOI18_doll) C++14
100 / 100
 138 ms 13672 KB 
#include "doll.h"
#include<vector>

using namespace std;

#define MAXN 200000

int l[4*MAXN], r[4*MAXN], num[4*MAXN], numn=0;
bool chk[4*MAXN];

void create_circuit(int M, vector<int> A) {
	A.push_back(0);
	int N=A.size();
	vector<int> C(M+1, -1), X, Y;
	int two;
	int cnt=0;

	if(N==2){
		C[0]=A[0];
		C[A[0]]=0;
		answer(C, X, Y);
		return;
	}

	for(two=0; (1<<two)<N; two++);
	l[1]=0;
	r[1]=(1<<two)-1;
	for(int i=2; i<(1<<two+1); i++){
		if(i%2==0){
			l[i]=l[i/2];
			r[i]=(l[i/2]+r[i/2])/2;
		}
		else{
			l[i]=(l[i/2]+r[i/2])/2+1;
			r[i]=r[i/2];
		}
	}
	//for(int i=1; i<(1<<two); i++) printf("%d %d\n", l[i], r[i]);
	for(int i=1; i<(1<<two); i++){
		if(r[i]>=(1<<two)-N){
			num[i]=--numn;
			X.push_back(-1);
			Y.push_back(-1);
		}
		else num[i]=-1;
	}
	//for(int i=1; i<(1<<two); i++) printf("%d ", num[i]);
	for(int i=1; i<(1<<two-1); i++) if(r[i]>=(1<<two)-N&&l[i]<r[i]){
		X[-num[i]-1]=num[i*2];
		Y[-num[i]-1]=num[i*2+1];
	}
	for(int i=0; i<(1<<two); i++){
		int k;
		for(k=1; k<(1<<two)&&r[k]>=(1<<two)-N;){
			chk[k]=!chk[k];
			k=k*2+(chk[k]?0:1);
		}
		//printf("[%d]\n", k);
		if(r[k]>=(1<<two)-N){
			//printf("*");
			if(k%2==0) X[-num[k/2]-1]=A[cnt++];
			else Y[-num[k/2]-1]=A[cnt++];
		}
	}
	answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:28:24: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   28 |  for(int i=2; i<(1<<two+1); i++){
      |                     ~~~^~
doll.cpp:48:24: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   48 |  for(int i=1; i<(1<<two-1); i++) if(r[i]>=(1<<two)-N&&l[i]<r[i]){
      |                     ~~~^~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 51 ms 6416 KB Output is correct
3 Correct 46 ms 6440 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 18 ms 1484 KB Output is correct
6 Correct 65 ms 8208 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 2 ms 204 KB Output is correct
2 Correct 51 ms 6416 KB Output is correct
3 Correct 46 ms 6440 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 18 ms 1484 KB Output is correct
6 Correct 65 ms 8208 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 81 ms 10812 KB Output is correct
9 Correct 106 ms 11280 KB Output is correct
10 Correct 138 ms 13672 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 2 ms 204 KB Output is correct
2 Correct 51 ms 6416 KB Output is correct
3 Correct 46 ms 6440 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 18 ms 1484 KB Output is correct
6 Correct 65 ms 8208 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 81 ms 10812 KB Output is correct
9 Correct 106 ms 11280 KB Output is correct
10 Correct 138 ms 13672 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 109 ms 13156 KB Output is correct
15 Correct 79 ms 10292 KB Output is correct
16 Correct 116 ms 12896 KB Output is correct
17 Correct 2 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 127 ms 13308 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 2 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 71 ms 9696 KB Output is correct
3 Correct 85 ms 9672 KB Output is correct
4 Correct 110 ms 11840 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 71 ms 9696 KB Output is correct
3 Correct 85 ms 9672 KB Output is correct
4 Correct 110 ms 11840 KB Output is correct
5 Correct 131 ms 12716 KB Output is correct
6 Correct 123 ms 12380 KB Output is correct
7 Correct 107 ms 12512 KB Output is correct
8 Correct 104 ms 12156 KB Output is correct
9 Correct 85 ms 9684 KB Output is correct
10 Correct 102 ms 12140 KB Output is correct
11 Correct 100 ms 11796 KB Output is correct
12 Correct 67 ms 9704 KB Output is correct
13 Correct 96 ms 9996 KB Output is correct
14 Correct 81 ms 10016 KB Output is correct
15 Correct 70 ms 10112 KB Output is correct
16 Correct 4 ms 588 KB Output is correct
17 Correct 66 ms 8332 KB Output is correct
18 Correct 68 ms 9592 KB Output is correct
19 Correct 67 ms 9720 KB Output is correct
20 Correct 130 ms 11960 KB Output is correct
21 Correct 109 ms 11816 KB Output is correct
22 Correct 120 ms 11832 KB Output is correct