Submission #459486

#	Time	Username	Problem	Language	Result	Execution time	Memory
459486		Khizri	동굴 (IOI13_cave)	C++17	100 / 100	1216 ms	548 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back		 
#define F first																 
#define S second 															 
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=5000+5;
int a[mxn],b[mxn],color[mxn],l,r,val,ind;
void ask(int &l,int &r,int k,int n){
	int m=(l+r)/2;
	for(int i=0;i<n;i++){
		if(!color[i]){
			a[i]=1-k;
		}
	}
	for(int i=l;i<=m;i++){
		if(!color[i]){
			a[i]=k;
		}
	}
	int ans=tryCombination(a);
	if(ans==val){
		r=m-1;
		ind=m;
	}
	else{
		l=m+1;
	}
}
void exploreCave(int n) {
	//tryCombination(a);
    for(int i=0;i<n;i++){
    	val=i;
    	for(int j=0;j<n;j++){
			if(!color[j]){
				a[j]=0;
			}
		}
		int k=0;
    	if(tryCombination(a)!=i){
			for(int j=0;j<n;j++){
				if(!color[j]){
					a[j]=1;
					k=1;
				}
			}
		}
		l=0,r=n-1;
		while(l<=r){
			ask(l,r,k,n);
		}
		color[ind]=1;
		b[ind]=i;
		a[ind]=1-k;
	}
	answer(a,b);
}

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