Submission #171717

#	Time	Username	Problem	Language	Result	Execution time	Memory
171717		Lukoloz	Cave (IOI13_cave)	C++14	100 / 100	528 ms	588 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
#define ll long long 
#define ff first
#define ss second
#define MAXN 5005
#define pb push_back
using namespace std;
// int nn,cor[MAXN],cord[MAXN],per[MAXN];
// int tryCombination(bool comb[]){
//     bool temp1[nn];
//     for (int i=0; i<nn; i++){
//         cout<<comb[i]<<" ";
//         temp1[per[i]]=comb[i];
//     }
//     for (int i=0; i<nn; i++){
//         if (temp1[i]!=cord[i]) { cout<<" - "<<i<<endl; return i; }
//     }
//     cout<<" - "<<-1<<endl;
//     return -1;
// }
// void answer(bool comb[],int ans[]){
//     for (int i=0; i<nn; i++) cout<<comb[i]<<" "; cout<<endl;
//     for (int i=0; i<nn; i++) cout<<ans[i]<<" "; cout<<endl;
// }
void exploreCave(int n){
    int fl[n],comb[n],closp;
    int ans[n],bl,br,bm;
    for (int i=0; i<n; i++) fl[i]=0;
    for (int i=0; i<n; i++){

        // cout<<" -- "<<i<<" -- "<<endl;

        for (int j=0; j<n; j++){
            if (fl[j]) continue;
            comb[j]=0;
        }

        // cout<<"comb array - ";  for (int j=0; j<n; j++) cout<<comb[j]<<" "; cout<<endl;
        
        if (tryCombination(comb)!=i){
            for (int j=0; j<n; j++){
                if (fl[j]) continue;
                comb[j]=1;
            }
            closp=1;
        } else closp=0;

        // cout<<"closp - "<<closp<<endl;
        
        bl=0; br=n-1;
        while(bl<br){
            bm=(bl+br)/2;
            for (int j=bl; j<=bm; j++){
                if (fl[j]) continue;
                comb[j]=!closp;
            }
            if (tryCombination(comb)!=i) br=bm;
            else bl=bm+1;
            for (int j=bl; j<=bm; j++){
                if (fl[j]) continue;
                comb[j]=closp;
            }
        }
        ans[bl]=i;
        comb[bl]=!closp;
        // cout<<bl<<endl;
        // cout<<comb[bl]<<endl;
        fl[bl]=1;

    }

    answer(comb,ans);
    
}
// int main(){
//     cin>>nn;
//     for (int i=0; i<nn; i++) cin>>cor[i];
//     for (int i=0; i<nn; i++) cin>>per[i];
//     for (int i=0; i<nn; i++) cord[per[i]]=cor[i];
//     exploreCave(nn);
// }
/*
4
1 1 1 0
3 1 0 2
*/

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