Submission #849166

#	Time	Username	Problem	Language	Result	Execution time	Memory
849166		abcvuitunggio	Cave (IOI13_cave)	C++17	0 / 100	104 ms	600 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int S[5000],D[5000],ch[5000];
vector <int> v;
void exploreCave(int N){
    for (int i=0;i<N;i++){
        v.clear();
        for (int j=0;j<N;j++)
            if (!ch[j]){
                v.push_back(j);
                S[j]=0;
            }
        if (tryCombination(S)>i){
            int l=1,r=N-i,kq=-1,pos=0;
            while (l<=r){
                int mid=(l+r)>>1;
                if (mid<pos)
                    for (int i=mid;i<pos;i++)
                        S[v[i]]=0;
                else
                    for (int i=pos;i<mid;i++)
                        S[v[i]]=1;
                pos=mid;
                if (tryCombination(S)==i){
                    kq=v[mid-1];
                    r=mid-1;
                }
                else
                    l=mid+1;
            }
            S[kq]=0;
            ch[kq]=1;
            D[kq]=i;
        }
        else{
            int l=1,r=N-i,kq=-1,pos=0;
            while (l<=r){
                int mid=(l+r)>>1;
                if (mid<pos)
                    for (int i=mid;i<pos;i++)
                        S[v[i]]=0;
                else
                    for (int i=pos;i<mid;i++)
                        S[v[i]]=1;
                pos=mid;
                if (tryCombination(S)>i){
                    kq=v[mid-1];
                    r=mid-1;
                }
                else
                    l=mid+1;
            }
            S[kq]=ch[kq]=1;
            D[kq]=i;
        }
    }
    answer(S,D);
}

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