Submission #173215

#	Time	Username	Problem	Language	Result	Execution time	Memory
173215		mohammad	Cave (IOI13_cave)	C++14	100 / 100	447 ms	640 KiB

cave

/*
░░░░██████████████████
░░▄███████▀▀▀▀▀▀███████▄
░▐████▀▒mohammad▒▀██████▄
░███▀▒▒▒▒alaa▒▒▒▒▒▒▀█████
░▐██▒▒▒alwrawrah▒▒▒▒▒████▌
░▐█▌▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒████▌
░░█▒▄▀▀▀▀▀▄▒▒▄▀▀▀▀▀▄▒▐███▌
░░░▐░░░▄▄░░▌▐░░░▄▄░░▌▐███▌
░▄▀▌░░░▀▀░░▌▐░░░▀▀░░▌▒▀▒█▌
░▌▒▀▄░░░░▄▀▒▒▀▄░░░▄▀▒▒▄▀▒▌
░▀▄▐▒▀▀▀▀▒▒▒▒▒▒▀▀▀▒▒▒▒▒▒█
░░░▀▌▒▄██▄▄▄▄████▄▒▒▒▒█▀
░░░░▄██████████████▒▒▐▌
░░░▀███▀▀████▀█████▀▒▌
░░░░░▌▒▒▒▄▒▒▒▄▒▒▒▒▒▒▐
░░░░░▌▒▒▒▒▀▀▀▒▒▒▒▒▒▒▐
*/	
 
#include<bits/stdc++.h>
#include "cave.h"
using namespace std;
 
typedef long long ll ;
const ll oo = 4294967296;
const double PI = acos(-1);
const ll M = 998244353;

int s[5010] , d[5010] , vis[5010];

void exploreCave(int N){
	for(int i = 0 ; i < N; ++i){
		int x = tryCombination(s);
		bool b = (x > i || x == -1 ? 0 : 1);
		int lo = 0 , hi = N - 1 ;
		while(lo != hi){
			int md = (lo + hi) / 2 ;
			int idx = lo ;
			while(idx <= md){
				if(!vis[idx])
					s[idx] = !s[idx];
				idx++;
			}
			x = tryCombination(s);
			bool ps = (x > i || x == -1 ? 0 : 1);
			idx = lo ;
			while(idx <= md){
				if(!vis[idx])
					s[idx] = !s[idx];
				idx++;
			}
			if(b != ps)
				hi = md;
			else
				lo = md + 1;
		}
		d[lo] = i ;
		s[lo] = b ;
		vis[lo] = 1;
	}
	answer(s , d);
}

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