Submission #303964

#	Time	Username	Problem	Language	Result	Execution time	Memory
303964		rocks03	Cave (IOI13_cave)	C++14	100 / 100	251 ms	508 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int) (x).size())
using namespace std;

void answer(int S[], int D[]);
int tryCombination(int S[]);

void recur(int l, int r, int res, vector<int>&v, int S[], int D[]){
    if(l == r){
        if(res == -1){
            S[v[l]] ^= 1;
            D[v[l]] = tryCombination(S);
            S[v[l]] ^= 1;
        } else{
            D[v[l]] = res;
            S[v[l]] ^= 1;
        }
        v.erase(find(v.begin(), v.end(), v[l]));
        return;
    }
    int m = (l + r) / 2;
    for(int i = l; i <= m; i++){
        S[v[i]] ^= 1;
    }
    int res2 = tryCombination(S);
    for(int i = l; i <= m; i++){
        S[v[i]] ^= 1;
    }
    if(res == res2){
        recur(m+1, r, res, v, S, D);
        return;
    }
    if(res2 == -1 || res2 > res){
        recur(l, m, res, v, S, D);
        return;
    }
    if(res2 < res){
        for(int i = l; i <= m; i++){
            S[v[i]] ^= 1;
        }
        recur(l, m, res2, v, S, D);
        return;
    }
}

void exploreCave(int N){
    int S[N], D[N];
    memset(S, 0, sizeof(S));
    memset(D, -1, sizeof(D));
    vector<int> v(N);
    iota(v.begin(), v.end(), 0);
    while(SZ(v)){
        recur(0, SZ(v) - 1, tryCombination(S), v, S, D);
    }
    answer(S, D);
}

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