Submission #949820

#	Time	Username	Problem	Language	Result	Execution time	Memory
949820		emad234	Cave (IOI13_cave)	C++17	100 / 100	1000 ms	604 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<int,int>
const int mod = 1e9 + 7;
const int mxN = 2e5 + 5;
using namespace std;
int tryCombination(int S[]);
void answer(int S[], int D[]);
void exploreCave(int N);
void exploreCave(int N) {
    const int sz = N;
    int s[sz],d[sz];
    int gv[sz];
    memset(s,-1,sizeof s);
    for(int i = 0;i < N;i++){
        bool chk = 0;
        for(int j = 0;j < N;j++){
            gv[j] = s[j] != -1 ? s[j] : chk;
        }
        if(tryCombination(gv) == i)  chk = 1;
        int l = 0,r = N - 1;
        while(l < r){
            int md = (l + r) / 2;
            for(int j = 0;j < N;j++) gv[j] = s[j] != -1 ? s[j] : !chk;
            for(int j = l;j <= md;j++) gv[j] = s[j] != -1 ? s[j] : chk;
            if(tryCombination(gv) == i){
                l = md + 1;
            }else{
                r = md;
            }
        }
        s[l] = chk;
        d[l] = i;
    }
    answer(s,d);
}

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