Submission #562973

#	Time	Username	Problem	Language	Result	Execution time	Memory
562973		Deepesson	Cave (IOI13_cave)	C++17	100 / 100	396 ms	656 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"

#define MAX 5005
int tryCombination(int S[]);
void answer(int S[], int D[]);
void exploreCave(int N);


bool skip[MAX];
bool padrao[MAX];
int relacao[MAX];
int n;
int tentar(int l=-1,int r=-1){
    int combinacao[n];
    for(int i=0;i!=n;++i)combinacao[i]=padrao[i];
    if(l!=-1){
        for(int j=l;j<=r;++j){
            if(skip[j])continue;
            ///Ativar chave
            combinacao[j]=1;
        }
    }
    return tryCombination(combinacao);
}
int lessthan(int la,int ra,int obj){
    if(la==ra){
        return la;
    }
    int m = (la+ra)/2;
    int x = tentar(la,m);
    if(x<=obj&&x!=-1){
        return lessthan(la,m,obj);
    }else return lessthan(m+1,ra,obj);
}
int atleast(int la,int ra,int obj){
    if(la==ra){
        return la;
    }
    int m = (la+ra)/2;
    int x = tentar(la,m);
    if(x>obj||x==-1){
        return atleast(la,m,obj);
    }else return atleast(m+1,ra,obj);
}
void exploreCave(int N) {
    n=N;
    for(int i=0;i!=N;++i){
        int val = tentar();
        int ind=-1;
        int esperado=-1;

        if(val>i||val==-1){///Tentar botar o valor para i-1 (Garantido que 1 eh a chave primaria)
            esperado=0;
            ind = lessthan(0,N-1,i);
        }else {///Tentar botar o valor para pelo menos i (Garantido que 0 eh a chave primaria)
            esperado=1;
            ind = atleast(0,N-1,i);
        }


        skip[ind]=true;

        padrao[ind]=esperado;

        relacao[ind]=i;
    }
    int ans1[N],ans2[N];
    for(int i=0;i!=N;++i){
        ans1[i]=padrao[i];
        ans2[i]=relacao[i];
    }
    answer(ans1,ans2);
}

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