Submission #907465

#	Time	Username	Problem	Language	Result	Execution time	Memory
907465		Mathias	Cave (IOI13_cave)	C++14	100 / 100	546 ms	1104 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
const int MAXN = 5e3+7;
int t1[MAXN], t2[MAXN], res[MAXN], t3[MAXN];
int xd,p,k,s;
/*int n;
int comb[MAXN], dop[MAXN],sol[MAXN];
int tryCombination(int t[]){
    for(int i=0;i<n;i++) if(t[i]!=sol[i]) return i;
    return -1;
}
void answer(int a[],int b[]){
    for(int i=0;i<n;i++) if(a[i]!=comb[i]) {cout<<"WA\n"; return;}
    for(int i=0;i<n;i++) if(b[i]!=dop[i]){cout<<"WA\n"; return;}
    cout<<"OK\n";
}*/
void exploreCave(int N){
    for(int i=0;i<N;i++){
        xd=0,p=0,k=N-1;
        for(int j=0;j<N;j++) t1[j]=0;
        for(int j=0;j<i;j++) t1[t3[j]]=t2[t3[j]];
        if(tryCombination(t1)==i) xd++;
        while(p<k){
            s=(p+k)/2;
            for(int j=0;j<N;j++) t1[j]=1-xd;
            for(int j=p;j<=s;j++) t1[j]=xd;
            for(int j=0;j<i;j++) t1[t3[j]]=t2[t3[j]];
            if(tryCombination(t1)==i) p=s+1;
            else k=s;
        }
        //cout<<"p="<<p<<'\n';
        t3[i]=p;
        t2[t3[i]]=xd;
    }
    for(int i=0;i<N;i++) res[t3[i]]=i;
    //for(int i=0;i<n;i++) cout<<t2[i]<<' '; cout<<'\n';
    //for(int i=0;i<n;i++) cout<<res[i]<<' '; cout<<'\n';
    answer(t2,res);
}/*
int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>comb[i];
    for(int i=0;i<n;i++) cin>>dop[i];
    for(int i=0;i<n;i++) sol[dop[i]]=comb[i];
    for(int i=0;i<n;i++) cout<<sol[i]<<' ';
    exploreCave(n);
    return 0;   
}*/

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