Submission #29929

#	Time	Username	Problem	Language	Result	Execution time	Memory
29929		inqr	Cave (IOI13_cave)	C++14	100 / 100	1408 ms	640 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define rt insert
#define st first
#define nd second
#define ll long long
#define DB printf("debug\n");
using namespace std;
int n;
vector < pair<int,int> > sw_st(5000);//sw i 1 -> st kapi nd state
vector < int > sw_nf;
int last_try[5000];
int new_try[5000];
int last_try_ret;
int new_try_ret;
int last_try_state;
int new_try_state;
void try_dr(int dr){
	if(dr==0){
		memset(last_try,0,sizeof(last_try));
		memset(new_try,0,sizeof(new_try));
	}
	last_try_ret=tryCombination(last_try);
	last_try_state=	(last_try_ret>dr || last_try_ret==-1) ? 0 : 1;
	//printf("1:dr = %d drst=%d ltr=%d\n",dr,last_try_state,last_try_ret);

	int l=0,r=sw_nf.size()-1,m;
	while(l<r){
		for(int i=0;i<n;i++){	
			if(sw_st[i].nd==0){
				new_try[i]=1;
				//printf("new_try[%d]=%d\n",i,new_try[i]);
			}
			else if(sw_st[i].nd==1){
				new_try[i]=0;
				//printf("new_try[%d]=%d\n",i,new_try[i]);
			}
		}
		m=(l+r)/2;
		//printf("	dr =%d l=%d r=%d m=%d\n",dr,l,r,m);
		for(int i=l;i<=m;i++){
			new_try[sw_nf[i]]=!last_try[sw_nf[i]];
			//printf("	new_try[%d]=%d\n",sw_nf[i],new_try[sw_nf[i]]);
		}
		new_try_ret=tryCombination(new_try);
		new_try_state=(new_try_ret>dr || new_try_ret==-1) ? 0 : 1;

		if(last_try_state!=new_try_state){
			r=m;
		}
		else{
			l=m+1;
		}
		//printf("	dr=%d ret=%d kon eden l=%d r=%d\n",dr,new_try_ret,l,r);

		last_try_ret=new_try_ret;
		last_try_state=new_try_state;
		for(int i=0;i<n;i++){
			last_try[i]=new_try[i];
		}
	}
	int sw=sw_nf[l];
	//printf("2:sw=%d ltr=%d lts=%d\n",sw,last_try_ret,last_try_state);
	if(dr==last_try_ret){
		last_try[sw]=!last_try[sw];
	}
	if(last_try[sw]==1){
		sw_st[sw]=mp(dr,0);
	}
	else sw_st[sw]=mp(dr,1);
	//printf("3:sw=%d st=%d dr=%d st=%d\n",sw,1,dr,sw_st[sw].nd);
	sw_nf.erase(sw_nf.begin()+l);
}
void exploreCave(int N) {
	n=N;
	for(int i=0;i<n;i++){
		sw_nf.pb(i);//bilinmeyenlere ekle
		sw_st[i]=mp(-1,-1);
	}
    for(int i=0;i<n;i++){
    	try_dr(i);
    }
    int ans1[n],ans2[n];
    for(int i=0;i<n;i++){
    	if(sw_st[i].nd==0)ans1[i]=1;
    	else ans1[i]=0;
    	ans2[i]=sw_st[i].st;
    }
    answer(ans1,ans2);
}

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