oj.uz

Submission #82227

# Submission time Handle Problem Language Result Execution time Memory
82227 2018-10-29T14:33:57 Z KLPP Mechanical Doll (IOI18_doll) C++14
10 / 100
 71 ms 7684 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(200000);
vector<int> Y(200000);
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[200000];
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 2 ms 1868 KB Output is correct
2 Correct 57 ms 5320 KB Output is correct
3 Correct 48 ms 5064 KB Output is correct
4 Correct 2 ms 1868 KB Output is correct
5 Correct 12 ms 3020 KB Output is correct
6 Correct 71 ms 6668 KB Output is correct
7 Runtime error 8 ms 4172 KB Execution killed with signal 11

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1868 KB Output is correct
2 Correct 57 ms 5320 KB Output is correct
3 Correct 48 ms 5064 KB Output is correct
4 Correct 2 ms 1868 KB Output is correct
5 Correct 12 ms 3020 KB Output is correct
6 Correct 71 ms 6668 KB Output is correct
7 Runtime error 8 ms 4172 KB Execution killed with signal 11

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1868 KB Output is correct
2 Correct 57 ms 5320 KB Output is correct
3 Correct 48 ms 5064 KB Output is correct
4 Correct 2 ms 1868 KB Output is correct
5 Correct 12 ms 3020 KB Output is correct
6 Correct 71 ms 6668 KB Output is correct
7 Runtime error 8 ms 4172 KB Execution killed with signal 11

Subtask #4
10.0 / 10.0

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

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1864 KB Output is correct
2 Runtime error 28 ms 7684 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1864 KB Output is correct
2 Runtime error 28 ms 7684 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -