| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1313785 | Chinguun | 동굴 (IOI13_cave) | C++20 | 0 ms | 0 KiB |
#include "cave.h"
#define ff first
#define ss second
#define pb push_back
#define ppb pop_back
#define meta int tm = (tl + tr) / 2, x = i * 2 + 1, y = x + 1
const int N = 5007;
const int TN = 4 * N;
const int oo = 1e9;
const int mod = 1e9 + 7;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
const int NN = 5007;
int a[NN], n, ans1[NN], ans2[NN], k;
bool vis[NN];
int rev (int x) {
if (x) return 0;
return 1;
}
int rec (int l, int r, int p) {
if (l == r) return l;
int m = (l + r) / 2, re = rev(a[p]);
for (int i = m + 1; i <= r; i++)
if (!vis[i]) a[i] = re;
int c = tryCombination(a);
if (c > p || c == -1) return rec (l, m, p);
for (int i = m + 1; i <= r; i++) a[i] = k;
return rec (m + 1, r, p);
}
void exploreCave(int N) {
n = N;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) a[j] = 1;
for (int j = 0; j < n; j++) {
if (vis[j]) a[j] = ans1[j];
}
int b = tryCombination(a);
if (b > i || b == -1) k = 1;
else {
k = 0;
for (int j = 0; j < n; j++)
if (!vis[j]) a[i] = k;
}
int pos = rec(0, n - 1, i);
ans2[pos] = i;
ans1[pos] = k;
a[pos] = k;
vis[pos] = 1;
}
answer (ans1, ans2);
return;
}