Submission #383951

#	Time	Username	Problem	Language	Result	Execution time	Memory
383951		Keshi	Cave (IOI13_cave)	C++17	100 / 100	371 ms	748 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 N, a[maxn], b[maxn], c[maxn], aans[maxn], cans[maxn];
bool ok[maxn], bad[maxn];

/*int tryCombination(int S[]){
	fill(bad, bad + N, 0);
	for(ll i = 0; i < N; i++){
		if(aans[i] != S[i]) bad[cans[i]] = 1;
	}
	for(ll i = 0; i < N; i++){
		if(bad[i]) return i;
	}
	return -1;
}
void answer(int S[], int D[]){
	cout << "answer\n";
	for(ll i = 0; i < N; i++){
		cout << S[i] << " ";
	}
	cout << "\n";
	for(ll i = 0; i < N; i++){
		cout << D[i] << " ";
	}
	cout << "\n";
}*/

void exploreCave(int n) {
    for(ll i = 0; i < n; i++){
		//cout << "# " << i << "\n";
		for(ll j = 0; j < n; j++){
			b[j] = a[j];
		}
		/*for(ll o = 0; o < n; o++){
			cout << b[o] << " ";
		}*/
		ll x = tryCombination(b);
		//cout << " -> " << 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){
		//			cout << "$ " << m2 << "\n";
					if(!ok[m2]) b[m2] ^= 1;
					m2++;
				}
			}
			else{
				while(m2 - 1 > mid){
					m2--;
					if(!ok[m2]) b[m2] ^= 1;
				}
			}
		/*	cout << "! " << mid << "\n";
		for(ll o = 0; o < n; o++){
			cout << b[o] << " ";
		}*/
			ll y = tryCombination(b);
		//cout << " -> " << 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(){
    freopen("sample.in", "r", stdin);
	cin >> N;
	for(ll i = 0; i < N; i++){
		cin >> aans[i];
		cout << aans[i] << " ";
	}
	cout << "\n";
	for(ll i = 0; i < N; i++){
		cin >> cans[i];
		cout << cans[i] << " ";
	}
	cout << "\nstart\n";
	exploreCave(N);



    return 0;
}
*/

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