| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 328282 | arwaeystoamneg | 동굴 (IOI13_cave) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
fill(all(t), -1);
F0R(j, n)
{
if (ans[j] != -1)t[j] = state[j];
}
F0R(j, n)
{
if (t[j] != -1)continue;
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(state, ans);
}