Submission #383947

#	Time	Username	Problem	Language	Result	Execution time	Memory
383947		Keshi	Cave (IOI13_cave)	C++17	0 / 100	59 ms	492 KiB

cave

//In the name of God
#include <bits/stdc++.h>
#include "cave.h"
using namespace std;

typedef int ll;
typedef pair<ll, ll> pll;

const ll maxn = 5001;
const ll mod = 1e9 + 7;
const ll inf = 1e9;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()

ll a[maxn], b[maxn], c[maxn];
bool ok[maxn];

void exploreCave(int n) {
    for(ll i = 0; i < n; i++){
		for(ll j = 0; j < n; j++){
			b[j] = a[j];
		}
		ll x = tryCombination(b);
		if(x == -1) x = n;
		ll l = -1, r = n - 1, mid;
		ll m2 = 0;
		while(r - l > 1){
			mid = (l + r) >> 1;
			if(m2 < mid){
				while(m2 <= mid){
					if(!ok[m2]) b[m2] ^= 1;
					m2++;
				}
			}
			else{
				while(m2 - 1 > mid){
					m2--;
					if(!ok[m2]) b[m2] ^= 1;
				}
			}
          	m2 = mid;
			ll y = tryCombination(b);
			if(y == -1) y = n;
			if((x == i) == (y == i)) l = mid;
			else r = mid;
		}
		c[r] = i;
		ok[r] = 1;
		if(x == i) a[r] = 1;
	}
	answer(a, c);
}


/*int main(){
    fast_io;



    return 0;
}*/

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