| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 555293 | urosk | Cave (IOI13_cave) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>
#define ld double
#define ll int
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
using namespace std;
int tryCombination(int S[]);
void answer(int S[], int D[]);
void exploreCave(int N);
#define maxn 5005
ll n;
ll a[maxn];
ll b[maxn];
ll c[maxn];
void exploreCave(int N) {
n = N;
for(ll i = 0;i<n;i++) b[i] = -1;
for(ll i = 0;i<n;i++) c[i] = 0;
if(tryCombination(c)==-1){
for(ll i = 0;i<n;i++) c[i] = 1;
for(ll i = 0;i<n;i++){
ceri(b,0,n-1);
for(ll j = 0;j<n;j++){
if(b[j]!=-1) continue;
c[j] = 0;
ll e = tryCombination(c);
//ceri(c,0,n-1);
//cerr<<j<< " "<<e<<endl;
if(i==n-1){
if(e==-1){
b[j] = i;
answer(a,b);
}
}else{
if(e>i){
b[j] = i;
goto lol;
}
}
c[j] = 1;
}
lol:;
}
}
iota(a,a+n,0);
for(ll i = 0;i<n;i++){
c[i] = 1;
ll e = tryCombination(c);
c[i] = 0;
ll f = tryCombination(c);
if(f==-1) f = n+1;
if(e==-1) e = n+1;
if(e>f) c[i] = 1;
else c[i] = 0;
}
answer(c,a);
}
#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;
}
num_calls = 0;
return N;
}
int main() {
int N;
N = init();
exploreCave(N);
printf("INCORRECT\nYour solution did not call answer().\n");
return 0;
}