Submission #301353

#	Time	Username	Problem	Language	Result	Execution time	Memory
301353		peti1234	Cave (IOI13_cave)	C++17	100 / 100	373 ms	612 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
const int c=5002;
int par[c], t[c];
bool v[c];
/*
int b1;
void answer(int a[], int b[]) {
    for (int i=0; i<b1; i++) cout << a[i] << " ";
    cout << "\n";
    for (int i=0; i<b1; i++) cout << b[i] << " ";
    cout << "\n";
    return;
}
int tryCombination(int a[]) {
    for (int i=0; i<b1; i++) cout << a[i] << " ";
    cout << "\n";
    for (int i=0; i<b1; i++) if (a[i]==1) return i;
    return -1;
    //int x; cin >> x;
    //return x;
}
*/
void f(int a, int b) {
    for (int i=a; i<b; i++) if (!v[i]) t[i]=1-t[i];
}
bool jo(int p) {
    int x=tryCombination(t);
    if (x==-1) x=1e9;
    return x>p;
}
void exploreCave(int n) {
    for (int i=0; i<n; i++) {
        if (!jo(i)) f(0, n);
        int lo=0, hi=n;
        while(hi-lo>1) {
            int mid=(hi+lo)/2;
            f(mid, hi);
            if (jo(i)) hi=mid;
            else lo=mid, f(mid, hi);
        }
        par[lo]=i, v[lo]=1;
    }
    answer(t, par);
}

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