Submission #883875

#	Time	Username	Problem	Language	Result	Execution time	Memory
883875		Malix	Cave (IOI13_cave)	C++14	0 / 100	190 ms	524 KiB

cave

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

using namespace std;

typedef vector<int> vi;

#define REP(i,a,b) for(int i=a;i<b;i++)

void exploreCave(int N) {
    /* ... */
    int s[N],d[N];
    int a[N];
    int pos=0;int p1=0,p2=0;int k=N;
    int l=0,r=N-1;
    while(pos<N){
        REP(i,0,N)a[i]=0;
        while(N){
            k=(l+r)/2;
            REP(i,l,k+1)a[i]=1;
            REP(i,0,pos+1)a[d[i]]=s[d[i]];
            p1=tryCombination(a);
            REP(i,l,k+1)a[i]=0;
            REP(i,0,pos+1)a[d[i]]=s[d[i]];
            p2=tryCombination(a);
            if((p1==pos)^(p2==pos))r=k;
            else l=k;
            if(l==r){
                d[pos]=l;
                a[l]=0;
                p1=tryCombination(a);
                if(p1==pos)s[l]=1;
                else s[l]=0;
                break;
            }
        }
        pos++;
    }
    answer(s,d);
}

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