Submission #1310669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310669		nikoloz-ch	Cave (IOI13_cave)	C++20	100 / 100	285 ms	652 KiB

cave

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

vector<int> s;

int ask(vector<int> &p){
    int n = p.size();
    int pt[n];
    for(int i = 0; i < n; i++) pt[i]=p[i];
    return tryCombination(pt);
}

void exploreCave(int N){
    s.assign(N, -1);
    vector<int> d(N, -1);
    for(int o = 0; o < N; o++){
        vector<int> c;
        for(int i = 0; i < N; i++) if(s[i]==-1) c.push_back(i);
        vector<int> cur(N);
        for(int i = 0; i < N; i++) cur[i] = (s[i]==-1 ? 0 : s[i]);
        int r = ask(cur);
        int si = (r == -1 || r > o) ? 0 : 1;
        if(c.size()==1){
            int sw = c[0];
            s[sw]=si;
            d[sw]=o;
            continue;
        }
        vector<int> cr = c;
        while(cr.size()>1){
            int m = cr.size()/2;
            vector<int> le(cr.begin(), cr.begin()+m);
            vector<int> ri(cr.begin()+m, cr.end());
            for(int i = 0; i < N; i++) cur[i] = (s[i]==-1 ? 1-si : s[i]);
            for(int i : le) cur[i]=si;
            int res = ask(cur);
            if(res == -1 or res > o) cr = le; else cr = ri;
        }
        int sw = cr[0];
        s[sw]=si;
        d[sw]=o;
    }
    int St[N], Dt[N];
    for(int i = 0; i < N; i++){ St[i]=s[i]; Dt[i]=d[i]; }
    answer(St, Dt);
}

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