Submission #328285

#	Time	Username	Problem	Language	Result	Execution time	Memory
328285		arwaeystoamneg	Cave (IOI13_cave)	C++17	100 / 100	943 ms	652 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>
 
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
// warning: ld is rougly 2x slower than double. Proof: ld: https://oj.uz/submission/319677 double: https://oj.uz/submission/319678
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;
 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
 
#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define endl '\n'
#define test int testc;cin>>testc;while(testc--)
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353
const ld pi = 3.1415926535;
 
void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
 
int* get(vi& t)
{
	int* a = &t[0];
	return a;
}
int n;
vi ans, state;
void solve(int i)
{
	vi t(n, -1);
	int type = 0;
	F0R(j, n)
	{
		if (ans[j] != -1)t[j] = state[j];
	}
	F0R(j, n)if (t[j] == -1)t[j] = type;
	int result = tryCombination(get(t));
	assert(result == -1 || result >= i);
	if (result != -1 && result <= i)type = 1;
	int l = 0, r = n - 1;
	while (l < r)
	{
		int m = (l + r) / 2;
		F0R(j, n)
		{
			if (ans[j] != -1)t[j] = state[j];
          else
          {
			if (j <= m)t[j] = type; else t[j] = 1 - type;
            
          }
		}
		result = tryCombination(get(t));
		assert(result == -1 || result >= i);
		if (result == -1 || result > i)r = m;
		else l = m + 1;
	}
	ans[l] = i;
	state[l] = type;
}
void exploreCave(int temporary)
{
	n = temporary;
	ans.rsz(n, -1);
	state.rsz(n, -1);
	F0R(i, n)
	{
		solve(i);
	}
	answer(get(state), get(ans));
}

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