Submission #1165966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165966		guanex	Cave (IOI13_cave)	C++20	0 / 100	1 ms	324 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef pair<long long, long long> pll;
typedef pair<char, int> ci;
typedef pair<string, int> si;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
#define pb push_back
#define sz(a) ((int)a.size())
#define fi first
#define se second
#define whole(v) v.begin(), v.end()
#define rwhole(v) v.rbegin(), v.rend()
#define inf INT_MAX/2
#define fro front
#define pqueue priority_queue
#define llpc(x) __builtin_popcountll(x)
#define ipc(x) __builtin_popcount(x)
#define iclz(x) __builtin_clz(x)
#define llclz(x) __builtin_clzll(x)
#define ictz(x) __builtin_ctz(x)
#define llctz(x) __builtin_ctzll(x)

void exploreCave(int N) {
    int n = n;
    int ud[n], ans[n];
    memset(ud, -1, sizeof ud);
    memset(ans, -1, sizeof ans);
    for(int i = 0; i < n; ++i){
        int ask[n];
        for(int j = 0; j < n; ++j){
            if(ans[j] == -1){
                ask[j] = 0;
            }else{
                ask[j] = ud[ans[j]];
            }
        }
        int res = tryCombination(ask);
        int o = 0;
        if(res <= i && res > -1){
            o = 1;
        }
        int lo = -1;
        int hi = n;
        //cout << i << " " << o << endl;
        while(hi - lo > 1){
            int mid = lo + (hi - lo) / 2;
            for(int j = 0; j < n; ++j){
                if(ans[j] == -1){
                    ask[j] = abs(o - 1);
                }else{
                    ask[j] = ud[ans[j]];
                }
            }
            for(int j = 0; j <= mid; ++j){
                if(ans[j] == -1){
                    ask[j] = o;
                }
            }
            int res = tryCombination(ask);
            if(res <= i && res > -1){
                lo = mid;
            }else{
                hi = mid;
            }
        }
        ud[i] = o;
        ans[hi] = i;
    }
    int an[n];
    for(int j = 0; j < n; ++j){
        an[j] = ud[ans[j]];
    }
    answer(an, ans);
}

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