Submission #969856

#	Time	Username	Problem	Language	Result	Execution time	Memory
969856		elotelo966	Cave (IOI13_cave)	C++17	100 / 100	982 ms	860 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 int go(int deg){
	int cur=0;
	for(int i=0;i<n;i++){
		if(kesin[i])continue;
		if(deg==cur)return 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;
		
		while(l<=r){
			int m=(l+r)/2;
			change(l,m,1);
			int door_use=tryCombination(arr_use);
			rechange();
			if(ans[i]){
				if(door_use!=i)r=m-1;
				else l=m+1;
			}
			else{
				if(door_use!=i)l=m+1;
				else r=m-1;
			}
		}
		tut=go(l);
		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 ;
}

Compilation message (stderr)

cave.cpp: In function 'int go(int)':
cave.cpp:35:1: warning: control reaches end of non-void function [-Wreturn-type]
   35 | }
      | ^

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