Submission #1316897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316897		exoworldgd	Cave (IOI13_cave)	C++20	0 / 100	214 ms	512 KiB

cave

#include<bits/stdc++.h>
#include"cave.h"
#define ll long long
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
using namespace std;
void exploreCave(int n){
	int s[n],d[n];
	bool v[n];
	for(int i=0;i<n;i++)s[i]=0,d[i]=i,v[i]=0;
	auto ok=[&](int x,int r,int f)->bool{
		int t[n];
		for(int i=0;i<n;i++)t[i]=s[i];
		if(f)for(int i=0;i<=r;i++)if(!v[i])t[i]^=1;
		else for(int i=r+1;i<n;i++)if(!v[i])t[i]^=1;
		return tryCombination(t)!=x;
	};
	for(int i=0;i<n;i++){
		int pos=tryCombination(s),lk=0;
		if(pos==i)lk=1;
		int l=0,r=n-1,ans=0,m;
		while(l<=r)m=(l+r)>>1,ok(i,m,lk)?(ans=m,r=m-1):l=m+1;
		s[ans]^=lk,v[ans]=1,d[ans]=i;
	}
	answer(s,d);
}

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