| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1195859 | Nonbangkok | Cave (IOI13_cave) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
// #include "cave.h"
#define coutf(n, m) cout << fixed << setprecision(n) << m
#define forr(i, a, n) for (int i = a; i < n; i++)
#define forl(i, a, n) for (int i = a; i > n; i--)
#define macos ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define endll "\n"
#define sp " "
typedef long long ll;
using namespace std;
#define MAX_N 5000
#define MAX_CALLS 70000
#define fail(s, x...) do { \
fprintf(stderr, s "\n", ## x); \
exit(1); \
} while(0)
/* Symbol obfuscation */
#define N koala
#define realS kangaroo
#define realD possum
#define inv platypus
#define num_calls echidna
static int N;
static int realS[MAX_N];
static int realD[MAX_N];
static int inv[MAX_N];
static int num_calls;
void answer(int S[], int D[]) {
int i;
int correct = 1;
for (i = 0; i < N; ++i)
if (S[i] != realS[i] || D[i] != realD[i]) {
correct = 0;
break;
}
if (correct)
printf("CORRECT\n");
else
printf("INCORRECT\n");
for (i = 0; i < N; ++i) {
if (i > 0)
printf(" ");
printf("%d", S[i]);
}
printf("\n");
for (i = 0; i < N; ++i) {
if (i > 0)
printf(" ");
printf("%d", D[i]);
}
printf("\n");
exit(0);
}
int tryCombination(int S[]) {
int i;
if (num_calls >= MAX_CALLS) {
printf("INCORRECT\nToo many calls to tryCombination().\n");
exit(0);
}
++num_calls;
for (i = 0; i < N; ++i)
if (S[inv[i]] != realS[inv[i]])
return i;
return -1;
}
int init() {
int i, res;
// FILE *f = fopen("cave.in", "r");
// if (!f)
// fail("Failed to open input file.");
// res = fscanf(f, "%d", &N);
// for (i = 0; i < N; ++i) {
// res = fscanf(f, "%d", &realS[i]);
// }
// for (i = 0; i < N; ++i) {
// res = fscanf(f, "%d", &realD[i]);
// inv[realD[i]] = i;
// }
cin >> N;
forr(i,0,N)cin >> realS[i];
forr(i,0,N)cin >> realD[i], inv[realD[i]] = i;
num_calls = 0;
return N;
}
const int M = 5010;
int k;
int S[M],D[M],test[M];
bool fix[M];
void exploreCave(int n) {
forr(i,0,n){ // loop the door
// int i = 0;
k = (tryCombination(S)==i);
int l = 0, r = n - 1,m;
while(l<r){ // binary search to find the position of river
m = (l+r) >> 1;
forr(j,0,n){
if(fix[j])test[j] = S[j];
else if(l<=j&&j<=m)test[j] = k;
else test[j] = 1 - k;
// cout << test[j] << sp;
}
// cout << endll;
// cout << "B : " << l << sp << m << sp << r << sp << (tryCombination(test)==i) << endll;
if(tryCombination(test)==i)l = m + 1;
else r = m;
}
// cout << "STDOUT : ";
// cout << l << sp << m << sp << r << endll;
S[l] = k;
D[l] = i;
fix[l] = true;
}
answer(S,D);
}
int main() {
int N;
N = init();
exploreCave(N);
printf("INCORRECT\nYour solution did not call answer().\n");
return 0;
}