Submission #142559

#	Time	Username	Problem	Language	Result	Execution time	Memory
142559		ahmet	Cave (IOI13_cave)	C++14	100 / 100	341 ms	640 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
#define ll long long
#define rep(i,n) for(long long (i)=0;(i)<(n);++(i))
#define ref(i,a,b) for (long long (i)=(a); (i)<=(b); ++(i))
#define INF 0xFFFFFF
#define endl '\n'
#define pb push_back
#define mp make_pair
const unsigned int mod = 1e9+7;
const int mx=5005;
int s[mx],d[mx];
void exploreCave(int n){
	if(n==1){
		if(tryCombination(s)==-1)answer(s,d);
		s[0]=1;
		answer(s,d);
	}
	vector <int> lock(n);
	for(int i=0;i<n;++i){
		int l=0;
		int r=n-1;
		int now=-1;
		int cur=-1;
		bool firstt=1;
		while(l<r){
			if(firstt){
				cur=tryCombination(s);
				firstt=0;
			}
			else cur=now;
			int mid=(l+r)/2;
			for(int j=l;j<=mid;++j){
				if(!lock[j])s[j]=1-s[j];
			}
			now=tryCombination(s);
			if(cur==now or (cur!=i and now!=i)){
				l=mid+1;
			}
			else{
				r=mid;
			}
		}
		if(now==i)s[l]=1-s[l];
		lock[l]=1;
		d[l]=i;
	}

	answer(s,d);
}

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