Submission #1049298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049298		ArthuroWich	Cave (IOI13_cave)	C++17	100 / 100	145 ms	852 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
int ans[5005], anscor[5005], at[5005], cor[5005];
vector<int> a;
void find(int i, int n) {
    int c = 0, v;
    int s[n];
    for (int j = 0; j < i; j++) {
        s[at[j]] = cor[j];
    }
    for (int j : a) {
        s[j] = c;
    }
    v = tryCombination(s);
    if (v <= i && v != -1) {
        c = 1;
    }
    for (int j : a) {
        s[j] = c^1;
    }
    int l = 0, r = a.size()-1;
    while(l < r) {
        int m = (l+r)/2;
        for (int j = l; j <= m; j++) {
            s[a[j]] = c;
        }
        v = tryCombination(s);
        for (int j = l; j <= m; j++) {
            s[a[j]] = c^1;
        }
        if (v <= i && v != -1) {
            l = m+1;
        } else {
            r = m;
        }
    }
    at[i] = a[l];
    cor[i] = c;
    ans[a[l]] = i;
    anscor[a[l]] = c;
    a.erase(a.begin()+l);
}
void exploreCave(int n) {
    for (int i = 0; i < n; i++) {
        a.push_back(i);
    }
    for (int i = 0; i < n; i++) {
        find(i, n);
    }
    answer(anscor, ans);
}

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