Submission #849167

#	Time	Username	Problem	Language	Result	Execution time	Memory
849167		abcvuitunggio	Cave (IOI13_cave)	C++17	100 / 100	206 ms	1104 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int S[5000],D[5000],ch[5000];
vector <int> v;
bool check(int i){
    int val=tryCombination(S);
    return (val>i||val==-1);
}
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 (check(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 (!check(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 (check(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: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24