Submission #1289542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289542		m.zeeshanrashid	Cave (IOI13_cave)	C++20	100 / 100	211 ms	524 KiB

cave

#ifdef __AVX2__
#pragma GCC target "avx2"
#endif
#pragma GCC optimize "O3"
#pragma GCC optimize "unroll-loops"
#include <bits/stdc++.h>
#include "cave.h"
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
using namespace std;
// #define int long long
#define elif else if
#define all(l) begin(l),end(l)
#define rall(l) rbegin(l),rend(l)
#define append push_back
#define print(l) for(auto i:l) cout<<i<<' '; cout<<endl;
#define pprint(a,b) cout<<a<<' '<<b<<endl;
#define inp(l) for(auto &i:l) cin>>i;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define pai make_pair
#define endl "\n"
#define pii pair<int,int>
#define fi first
#define se second
#define vec vector

// const int mod=998244353;
const int mod1=998244353;
const int mod=1e9+7;
// const int N=2e5+5;

void exploreCave(int n){
	int sw[n],d[n];
	for(int i=0;i<n;i++) sw[i]=d[i]=-1;
	int qu[n];
	int temp;
	for(int i=0;i<n;i++){
		int st=0;
		for(int i=0;i<n;i++){
			if(sw[i]>=0) qu[i]=sw[i];
			else qu[i]=st;
		}
		temp=tryCombination(qu);
		if(temp>i or temp==-1){}
		else st=1-st;
		int l=0,r=n;
		// cout<<st<<endl;
		while(l+1<r){
			int m=(l+r-1)/2;
			for(int j=0;j<n;j++){
				if(sw[j]>-1) qu[j]=sw[j];
				elif(j>=l and j<=m) qu[j]=st;
				else qu[j]=1-st;
			}
			// cout<<i<<' '<<l<<' '<<r<<' '<<m<<endl;
			// print(qu)
			// cout<<endl;
			int temp=tryCombination(qu);
			if(temp>i or temp==-1) r=m+1;
			else l=m+1;
		}
		// cout<<i<<' '<<l<<' '<<st<<endl;
		sw[l]=st;
		d[l]=i;
	}
	answer(sw,d);
}

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