Submission #1266900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266900		WH8	Cave (IOI13_cave)	C++20	100 / 100	354 ms	520 KiB

cave

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

int s[5005], d[5005], temp[5005];
int N;

void flip(int l, int r){
	for(int i=l;i<=r;i++){
		if(d[i]==-1)s[i]=!s[i];
	}
}

int submit(){
	//~ for(int i=0;i<N;i++){
		//~ cout<<s[i]<<" ";
	//~ }
	int ret=tryCombination(s);
	if(ret==-1)ret=N;
	//~ cout<<" gives  "<<ret<<endl;
	return ret;
}

void exploreCave(int n) {
	N=n;
	//~ fill(s, s+5005, -1);
	fill(d, d+5005, -1);

	for(int t=0;t<n;t++){
		int l=-1, r=n-1, m;
		int bef=submit();
		assert(bef >= t);
		while(r-l>1){
			m=(l+r)/2;
			//~ printf("l %d r %d m %d\n", l,r,m);
			flip(0, m);
			int ret=submit();
			assert(ret >= t);
			if(bef > t){
				if(ret == t){
					r=m;
				}
				else l=m;
			}
			else {
				if(ret > t){
					r=m;
				}
				else l=m;
			}
			flip(0, m);
		}
		assert(d[r]==-1);
		if(bef==t)flip(r, r);

		d[r]=t;
	}
	//~ for(int i=0;i<n;i++){
		//~ cout<<s[i]<<" ";
	//~ }
	//~ cout<<endl;
	//~ for(int i=0;i<n;i++){
		//~ cout<<d[i]<<" ";
	//~ }
	//~ cout<<endl;
	answer(s, d);
}

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