Submission #882174

#	Time	Username	Problem	Language	Result	Execution time	Memory
882174		andro	Cave (IOI13_cave)	C++14	12 / 100	244 ms	684 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
/*
int n;
int S1[4]={1,1,1,0};
int D1[4]={3,1,0,2};
void answer(int S[],int D[]){
    for(int i=0;i<n;i++)cout<<S[i]<<" ";
    cout<<endl;
    for(int i=0;i<n;i++)cout<<D[i]<<" ";
    exit(0);
}
int tryCombination(int S[]){
    for(int i=0;i<n;i++){
        if(S[i]!=S1[i])return i;
    }
    return -1;
}*/
void exploreCave(int N) {
    int S[N];
    int D[N];
    for(int i=0;i<N;i++){
        S[i]=0;
    }
    for(int i=0;i<N;i++){
        int A=tryCombination(S);
        if(A==-1)break;
        if(A>=i+1){

        }
        else {
            S[i]=1;
        }
    }
    for(int i=0;i<N;i++){
        int l=0,r=N-1,p=-1;
        while(l<=r){
            int mid=(l+r)/2;
            for(int j=mid+1;j<N;j++)S[j]^=1;
            int A=tryCombination(S);
            //cout<<i<<" "<<mid<<" "<<A<<" :::";
            //for(int j=0;j<N;j++)cout<<S[j];
            //cout<<endl;
            if(A==-1||A>=i+1){
                r=mid-1;
                p=mid;
            }
            else {
                l=mid+1;
            }
            for(int j=mid+1;j<N;j++)S[j]^=1;
        }
        D[p]=i;
    }
    answer(S,D);
}/*
signed main(){
    cin>>n;
    exploreCave(n);
}*/

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