oj.uz

Submission #82228

# Submission time Handle Problem Language Result Execution time Memory
82228 2018-10-29T14:42:57 Z KLPP Mechanical Doll (IOI18_doll) C++14
84 / 100
 154 ms 19244 KB 
#include "doll.h"
#include<iostream>
#include<vector>
using namespace std;
#define INF 10000000
int reverse(int a,int exp){
	int ans=0;
	while(exp--){ans*=2;
		ans+=a%2;
		a/=2;
	}//cout<<endl;
	return ans;
}
vector<int> X(1000000);
vector<int> Y(1000000);
int N;
int point;
void build(int level,int size){
	point--;
	if(level==1){
		if(size==2){
			X[-point-1]=-INF;
			Y[-point-1]=-INF;
		}else{
			X[-point-1]=-1;
			Y[-point-1]=-INF;
		}
		return;
	}
	int P=(1<<(level-1));
	if(size<=P){
		X[-point-1]=-1;
		Y[-point-1]=point-1;
		build(level-1,size);
		return;
	}int start=point;
	X[-start-1]=point-1;
	build(level-1,size-P);
	Y[-start-1]=point-1;
	build(level-1,P);
} 
int pointer;
vector<int> Sequence;
bool state[1000000];
void DFS(int node){
	//cout<<node<<endl;
	if(node==0)return;
	if(node<0){
		int num=-node-1;
		if(!state[num]){
			if(X[num]==-INF){
				X[num]=Sequence[pointer];
				pointer++;
			}state[num]=true;
			DFS(X[num]);
		}else{
			if(Y[num]==-INF){
				Y[num]=Sequence[pointer];
				pointer++;
			}state[num]=false;
			DFS(Y[num]);
		}
		return;
	}
	DFS(-1);
}

void create_circuit(int M, std::vector<int> A) {vector<int> C(M+1);
	A.push_back(0);
	for(int i=0;i<=M;i++)C[i]=-1;
	C[0]=A[0];
	A.erase(A.begin());
	N = A.size();
	int pow=1;
	int exp=0;
	while(pow<N){
		pow*=2;
		exp++;
	}point=0;
	build(exp,N);
	pointer=0;
	for(int i=0;i<N;i++)Sequence.push_back(A[i]);
	for(int i=0;i<2*N;i++)state[i]=false;
	DFS(-1);
	while(X.size()>-point){
		X.pop_back();
		Y.pop_back();
	}
	//cout<<exp<<endl;
	/*for(int i=0;i<-point;i++){
		cout<<X[i]<<" "<<Y[i]<<endl;
	}*/
	/*for(int i=0;i<pow/2-1;i++){
		X[i]=2*(-i-1);
		Y[i]=2*(-i-1)-1;
		//cout<<-i-1<<" "<<X[i]<<" "<<Y[i]<<endl;
	}
	for(int i=pow/2;i<pow;i++){
		int orderX=2*i-pow;
		int orderY=2*i+1-pow;
		//cout<<orderX<<" "<<orderY<<endl;
		//cout<<reverse(orderX,exp)<<endl;
		//cout<<reverse(orderY,exp)<<endl;
		int rX=reverse(orderX,exp);
		int rY=reverse(orderY,exp);
		//cout<<rX<<" "<<rY<<endl;
		if(rX+N>=pow){
			X[i-1]=A[rX-pow+N];
		}else X[i-1]=-1;
		if(rY+N>=pow){
			Y[i-1]=A[rY-pow+N];
		}else Y[i-1]=-1;
	}*/
	//cout<<pow<<endl;
	answer(C,X,Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:85:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   85 |  while(X.size()>-point){
      |        ~~~~~~~~^~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8012 KB Output is correct
2 Correct 54 ms 11572 KB Output is correct
3 Correct 52 ms 11220 KB Output is correct
4 Correct 5 ms 8140 KB Output is correct
5 Correct 16 ms 9292 KB Output is correct
6 Correct 76 ms 13020 KB Output is correct
7 Runtime error 26 ms 19244 KB Execution killed with signal 11

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8012 KB Output is correct
2 Correct 54 ms 11572 KB Output is correct
3 Correct 52 ms 11220 KB Output is correct
4 Correct 5 ms 8140 KB Output is correct
5 Correct 16 ms 9292 KB Output is correct
6 Correct 76 ms 13020 KB Output is correct
7 Runtime error 26 ms 19244 KB Execution killed with signal 11

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8012 KB Output is correct
2 Correct 54 ms 11572 KB Output is correct
3 Correct 52 ms 11220 KB Output is correct
4 Correct 5 ms 8140 KB Output is correct
5 Correct 16 ms 9292 KB Output is correct
6 Correct 76 ms 13020 KB Output is correct
7 Runtime error 26 ms 19244 KB Execution killed with signal 11

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8012 KB Output is correct
2 Correct 84 ms 13116 KB Output is correct
3 Correct 88 ms 12604 KB Output is correct
4 Correct 142 ms 15084 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8012 KB Output is correct
2 Correct 84 ms 13116 KB Output is correct
3 Correct 88 ms 12604 KB Output is correct
4 Correct 142 ms 15084 KB Output is correct
5 Correct 152 ms 16208 KB Output is correct
6 Correct 127 ms 16164 KB Output is correct
7 Correct 148 ms 16184 KB Output is correct
8 Correct 135 ms 15900 KB Output is correct
9 Correct 93 ms 12552 KB Output is correct
10 Correct 129 ms 15780 KB Output is correct
11 Correct 125 ms 15404 KB Output is correct
12 Correct 82 ms 12856 KB Output is correct
13 Correct 84 ms 13624 KB Output is correct
14 Correct 93 ms 13372 KB Output is correct
15 Correct 87 ms 13504 KB Output is correct
16 Correct 9 ms 8268 KB Output is correct
17 Correct 83 ms 13392 KB Output is correct
18 Correct 86 ms 13380 KB Output is correct
19 Correct 85 ms 12872 KB Output is correct
20 Correct 138 ms 15584 KB Output is correct
21 Correct 154 ms 15432 KB Output is correct
22 Correct 134 ms 15472 KB Output is correct