Submission #222902

#	Time	Username	Problem	Language	Result	Execution time	Memory
222902		kshitij_sodani	Cave (IOI13_cave)	C++17	100 / 100	1024 ms	920 KiB

cave

#include<iostream>
#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
#include "cave.h"
vector<int> kk;
int ans[5001];
int nn;
/*void answer(vector<int> x,vector<int> y){
	for(int i=0;i<nn;i++){
		cout<<x[i]<<",";
	}
	for(int i=0;i<nn;i++){
		cout<<y[i]<<",";
	}
}
int tryCombination(vector<int> x){
	for(int i=0;i<nn;i++){
		cout<<x[i]<<":";
	}

	int yy;
	cin>>yy;
	return yy;
}
*/

int find(int l,int r,int val,int mi){
//	cout<<l<<" "<<r<<endl;
	if(l==r){
		return kk[l];
	}
	int mid=(l+r)/2;
/*	for(int i=0;i<nn;i++){
		cout<<kk[i]<<",";
	}
	cout<<endl;*/
	int ans3[nn];
	for(int i=0;i<nn;i++){
		if(ans[i]!=-1){
			ans3[i]=ans[i];
			continue;
		}
		if(i<kk[l] or i>kk[mid]){
			ans3[i]=1-val;
		}
		else{
			ans3[i]=val;
		}
	}
	int tt=tryCombination(ans3);
	if(tt==-1 or tt>mi){
		return find(l,mid,val,mi);
	}
	else{
		return find(mid+1,r,val,mi);
	}
}
void exploreCave(int n){
	nn=n;
	for(int i=0;i<n;i++){
		ans[i]=-1;
	}
	int stat[n];
	for(int i=0;i<n;i++){
		int ans2[n];
		for(int j=0;j<n;j++){
			if(ans[j]==-1){
				ans2[j]=0;
			}
			else{
				ans2[j]=ans[j];
			}
		}
		int tt=tryCombination(ans2);
		int ss=1;

		if(tt==-1 or tt>i){
			ss=0;
		}
		kk.clear();
		for(int i=0;i<n;i++){
			if(ans[i]==-1){
				kk.pb(i);
			}
		}

		int ind=find(0,kk.size()-1,ss,i);
		stat[ind]=i;
		ans[ind]=ss;
	}
	int fin[n];
	for(int i=0;i<n;i++){
		fin[i]=ans[i];
	}
	answer(fin,stat);

}
/*int main(){

	exploreCave(4);

	return 0;
}

*/

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