Submission #982593

#	Time	Username	Problem	Language	Result	Execution time	Memory
982593		kwongweng	Cave (IOI13_cave)	C++17	100 / 100	230 ms	604 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef vector<vector<ll>> vll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define ms memset
#define fi first
#define se second

//Binary search

void exploreCave(int N) {
    int s[N]; ms(s,0,sizeof(s));
    int a[N], b[N]; ms(a,0,sizeof(a)); ms(b,-1,sizeof(b));
    FOR(i,0,N){
        int pos[N-i]; int cur = 0;
        FOR(j,0,N){
            if (b[j]==-1){
                s[j]=0; pos[cur]=j; cur++;
            }
            else s[j] = a[j];
        }
        int com = (tryCombination(s)==i);
        int l = 0, r = N-i; int ans;
        if (com){
            while (r-l>1){
                int mid = (l+r)/2;
                FOR(j,0,mid) s[pos[j]]=0;
                FOR(j,mid,N-i) s[pos[j]]=1;
                if (tryCombination(s)==i){
                    r=mid;
                }else{
                    l=mid;
                }
            }
            ans=l;
        }else{
            l=-1; r=N-i-1;
            while (r-l>1){
                int mid = (l+r)/2;
                FOR(j,0,mid+1) s[pos[j]]=0;
                FOR(j,mid+1,N-i) s[pos[j]]=1;
                if (tryCombination(s)==i){
                    l=mid;
                }else{
                    r=mid;
                }
            }
            ans=r;
        }
        
        b[pos[ans]] = i;
        a[pos[ans]] = com;
    }
    answer(a,b);
    /* ... */
}

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