Submission #1210203

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210203		boss_zz	Cave (IOI13_cave)	C++20	100 / 100	217 ms	516 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define ll long long 
#define ff first 
#define ss second 
#define mp make_pair 
using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll maxn=5005,inf=1e18;
int n,cur[maxn],D[maxn];
bitset<maxn> done;
void exploreCave(int NN){
    n=NN;
    rep(i,0,n-1){
        rep(j,0,n-1) if(!done[j]) cur[j]=1;
        ll l=0,r=n-1,Ans=r;
        int tmp=tryCombination(cur);
        bool con=(tmp>i||tmp==-1);
        while(r>=l){
            ll mid=(l+r)>>1;
            rep(j,l,mid) if(!done[j]) cur[j]=0;
            ll res=tryCombination(cur);
            if(res==-1) res=n;
            rep(j,l,mid) if(!done[j]) cur[j]=1;
            if((res>i)==con) l=mid+1;
            else Ans=mid,r=mid-1;
        }
        done[Ans]=1;
        D[Ans]=i;
        cur[Ans]=con;
    }
    answer(cur,D);
}

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