Submission #896478

#	Time	Username	Problem	Language	Result	Execution time	Memory
896478		sysia	Cave (IOI13_cave)	C++17	100 / 100	466 ms	816 KiB

cave

//Sylwia Sapkowska
#pragma GCC optimize("O3", "unroll-loops")
#include <bits/stdc++.h>
#include "cave.h"
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif


void exploreCave(int n) {
    vector<bool>fixed(n);
    int s[n], t[n], where[n];
    for (int i = 0; i<n; i++) s[i] = 0;
    
    for (int i = 1; i<=n; i++){
        int l = 0, r = n-1;
        int ans = 0;
        int curr = tryCombination(s);
        debug(i, curr);
        if (curr == -1) curr = n;
        while (r >= l){
            int mid = (l+r)/2;
            debug(mid);
            for (int j = 0; j<n; j++){
                t[j] = s[j];
                if (!fixed[j] && j <= mid){
                    t[j] = 1;
                }
            }
            int get = tryCombination(t);
            if (get == -1) get = n;
            if ((curr < i && get >= i) || (curr >= i && get < i)){
                ans = mid;
                r = mid-1;
            } else {
                l = mid+1;
            }
        }
        debug(i, ans);
        fixed[ans] = 1;
        where[ans] = i-1;
        s[ans] = (curr >= i ? 0 : 1);
    }
    answer(s, where);   
}

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