Submission #126571

#	Time	Username	Problem	Language	Result	Execution time	Memory
126571		kjp4155	Cave (IOI13_cave)	C++17	100 / 100	1037 ms	768 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;

#define sz(x) (int) x.size()

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

int S[10010], SS[10010], D[10010], E[10010];
int query[10010];

void fill_ans(int n){
    for(int i=0;i<n;i++){
        query[E[i]] = S[i];
    }
}

void divide(vector<int>& v1, vector<int>& v2, vector<int>& v3){
    v2.clear(); v3.clear();
    for(int i=0;i<sz(v1)/2;i++){
        v2.push_back(v1[i]);
    }
    for(int i=sz(v1)/2;i<sz(v1);i++){
        v3.push_back(v1[i]);
    }
}


void exploreCave(int N) {
    memset(D,-1,sizeof D);
    memset(E,-1,sizeof E);  
    for(int i=0;i<N;i++){
        int t;
        for(int j=0;j<N;j++) query[j] = 0;
        fill_ans(i);
        t = tryCombination(query);
        S[i] = (t>i || t==-1) ? 0 : 1;

        vector<int> v, v1, v2;
        for(int j=0;j<N;j++) if( D[j] == -1 ) v.push_back(j);
        while( sz(v) > 1 ){
            divide(v, v1, v2);
            for(int j=0;j<N;j++) query[j] = S[i]^1;
            for(auto e : v1) query[e] = S[i];
            fill_ans(i);

            t = tryCombination(query);
            if( t > i || t == -1 ) v = v1;
            else v = v2;
        }
        D[v[0]] = i;
        E[i] = v[0];
    }
    for(int i=0;i<N;i++){
        SS[E[i]] = S[i];
    }
    answer(SS,D);
}

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