Submission #855739

#	Time	Username	Problem	Language	Result	Execution time	Memory
855739		_uros9	Cave (IOI13_cave)	C++17	100 / 100	558 ms	1096 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN=5009;
int g_d[MAXN],i_odkljucava[MAXN]={0},probaj[MAXN],vrata_br[MAXN];
bool checked[MAXN]={0};
int n;
int N;
int S[MAXN],D[MAXN];

void kojeg_odkljucava(int br,int l,int d){
    if(l==d){
        i_odkljucava[l]=br;
        g_d[l]=vrata_br[br];
        checked[l]=true;
        return;
    }
    int s=(l+d)/2;
    for(int i=0; i<n; i++){
        if(checked[i]){
            probaj[i]=g_d[i];
            continue;
        }
        probaj[i]=1-vrata_br[br];
    }
    for(int i=l; i<=s; i++){
        if(checked[i]){
            probaj[i]=g_d[i];
            continue;
        }
        probaj[i]=vrata_br[br];
    }
    int ans=tryCombination(probaj);
    if(ans==-1||ans>br)
        kojeg_odkljucava(br,l,s);
    else
        kojeg_odkljucava(br,s+1,d);
}

void resavaj_za(int br){
    for(int i=0; i<n; i++){
        if(checked[i]){
            probaj[i]=g_d[i];
            continue;
        }
        probaj[i]=0;
    }
    int ans=tryCombination(probaj);
    if(ans==-1||ans>br)
        vrata_br[br]=0;
    else
        vrata_br[br]=1;
    kojeg_odkljucava(br,0,n);
    //cout << vrata_br[br] << endl;
}

void exploreCave(int N) {
    n=N;
    for(int i=0; i<n; i++){
        resavaj_za(i);
    }
    answer(g_d,i_odkljucava);
}

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