Submission #969857

#	Time	Username	Problem	Language	Result	Execution time	Memory
969857		elotelo966	Cave (IOI13_cave)	C++17	12 / 100	808 ms	604 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"

using namespace std;

#define lim 5005

int n,arr[lim],arr_use[lim];
bool kesin[lim];
int tut;

vector<int> deg;

inline void change(int l,int r,int val){
	int cur=0;
	deg.clear();
	for(int i=0;i<n;i++){
		if(kesin[i])continue;
		if(cur>=l && cur<=r){
			arr_use[i]=val;
			tut=i;
			deg.push_back(i);
		}
		cur++;
	}
}

inline void rechange(){
	for(auto ind:deg){
		arr_use[ind]=0;
	}
}

void exploreCave(int N) {
	n=N;
	int ans[n],ans2[n];
	
	for(int i=0;i<n;i++){
		int door=tryCombination(arr);
		if(door!=i)ans[i]=0; //cevap 0da
		else ans[i]=1; // cevap 1de
		int l=0,r=n-i-1;
		
		if(ans[i]){
			for(int i=0;i<n;i++){
				if(kesin[i])continue;
				arr_use[i]=1;
			}
		}
		
		while(l<=r){
			int m=(l+r)/2;
			change(l,m,ans[i]^1);
			int door_use=tryCombination(arr_use);
			rechange();
			if(door_use!=i){
				l=m+1;
				tut=m;
			}
			else r=m-1;
		}
		ans2[tut]=i;
		kesin[tut]=1;
		arr[tut]=ans[i];
		for(int i=0;i<n;i++){
			arr_use[i]=arr[i];
		}
		
	}
	
	int anss[n];
	
	for(int i=0;i<n;i++){
		anss[i]=ans[ans2[i]];
	}
	
	answer(anss,ans2);
	return ;
}

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