Submission #520308

#	Time	Username	Problem	Language	Result	Execution time	Memory
520308		new_acc	Cave (IOI13_cave)	C++14	100 / 100	1166 ms	672 KiB

cave

#include<bits/stdc++.h>
#include "cave.h"
#define ll long long
#define fi first
#define se second
using namespace std;
const int N=5000+10;
int aktres[N];
int vis[N];
int ans[N];
int n;
int pom[N];
int bs1(int i){
	int pocz=0,kon=n-1;
	int sr;
	int res=0;
	while(pocz<=kon){
		sr=(pocz+kon)/2;
		for(int j=0;j<n;j++){
			if(vis[j]) pom[j]=aktres[j];
			else pom[j]=0;
		}
		for(int j=0;j<=sr;j++) if(!vis[j]) pom[j]=1;
		int xd=tryCombination(pom);
		if(xd>i||xd==-1){
			res=sr;
			kon=sr-1;
		}else pocz=sr+1;
	}
	return res;
}
int bs2(int i){
	int pocz=0,kon=n-1;
	int sr;
	int res=0;
	while(pocz<=kon){
		sr=(pocz+kon)/2;
		for(int j=0;j<n;j++){
			if(vis[j]) pom[j]=aktres[j];
			else pom[j]=1;
		}
		for(int j=0;j<=sr;j++) if(!vis[j]) pom[j]=0;
		int xd=tryCombination(pom);
		if(xd>i||xd==-1){
			res=sr;
			kon=sr-1;
		}else pocz=sr+1;
	}
	return res;
}
void exploreCave(int m){
	n=m;
	for(int i=0;i<n;i++){
		int a=tryCombination(aktres);
		bool curr=(a==-1?1:a>i);
		curr^=1;
		int xd=0;
		if(curr) xd=bs1(i);
		else xd=bs2(i);
		aktres[xd]=curr;
		vis[xd]=1;
		ans[xd]=i;
	}

	answer(aktres,ans);
}

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