Submission #56765

#	Time	Username	Problem	Language	Result	Execution time	Memory
56765		hamzqq9	Cave (IOI13_cave)	C++14	12 / 100	370 ms	1152 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
using namespace std;

#define MAX 5005

#define sz(x) ((int)x.size())
#define pb push_back

int Q[MAX],S[MAX],state_of_door[MAX];
int N;

int solve(vector<int> &POS,int now,int VAL) {

	while(sz(POS)>1) {

		int mid=sz(POS)/2-1;

		for(int i=0;i<=mid;i++) {

			Q[POS[i]]=VAL;

		}

		for(int i=mid+1;i<sz(POS);i++) {

			Q[POS[i]]=!VAL;

		}

		int cur_door=tryCombination(Q);

		if(cur_door==now) {

			POS.erase(POS.begin(),POS.end()+mid+1);

		}
		else {

			POS.erase(POS.begin()+mid+1,POS.end());

		}

	}

	return POS[0];

}

void TRYIT(int now) {

	vector<int> POS;

	for(int i=0;i<now;i++) {

		Q[state_of_door[i]]=S[state_of_door[i]];

	}

	for(int i=0;i<N;i++) {

		if(~S[i]) continue ;

		Q[i]=0;

		POS.pb(i);

	}

	int cur_door=tryCombination(Q);

	int VAL=(cur_door==now);

	int pos_of_now=solve(POS,now,VAL);

	state_of_door[now]=pos_of_now;

	S[pos_of_now]=VAL;
 
}

void exploreCave(int N) {

	::N=N;

	for(int i=0;i<N;i++) S[i]=-1;

	for(int i=0;i<N;i++) {

		TRYIT(i);

	}

	int D[MAX];

	for(int i=0;i<N;i++) D[state_of_door[i]]=i;

	answer(S,D);

}

• Subtask 1: 12 / 12
• Subtask 2: 0 / 13
• Subtask 3: 0 / 21
• Subtask 4: 0 / 30
• Subtask 5: 0 / 24