Submission #1239842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239842		Minbaev	동굴 (IOI13_cave)	C++20	100 / 100	207 ms	652 KiB

cave

 #include "cave.h"
//#include "grader.c"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;
using namespace __gnu_pbds;

#define pb      push_back
#define all(x)  x.begin(),x.end()
#define ar      array
#define mrand(a, b)   uniform_int_distribution<int>(a, b)(rng)

template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}

template<class T> using ste = tree<T, null_type, less_equal<T>,
rb_tree_tag, tree_order_statistics_node_update>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

namespace FAST {
    template<typename T, typename F>
    istream &operator>>(istream &cin, pair<T, F> &p) {
        cin >> p.first >> p.second;
        return cin;
    }

    template<typename T, typename F>
    ostream &operator<<(ostream &cout, pair<T, F> &p) {
        cout << p.first << ' ' << p.second;
        return cout;
    }

    template<typename T>
    istream &operator>>(istream &cin, vector<T> &a) {
    for (T &i: a) cin >> i;
        return cin;
    }

    template<typename T>
    ostream &operator<<(ostream &cout, vector<T> &a) {
          for (T i: a) cout << i << ' ';
        return cout;
    }

    template<typename T>
    istream &operator>>(istream &cin, deque<T> &a) {
        for (T &i: a) cin >> i;
        return cin;
    }

    template<typename T>
    ostream &operator<<(ostream &cout, deque<T> &a) {
        for (T i: a) cout << i << ' ';
        return cout;
    }
}
using namespace FAST;

const long long inf = 1e17 + 7;
const int mod = 1e9 + 7;
const int md = 998244353;

int n,m,k;

void exploreCave(int N){

    int q[N];
    int val[N], ps[N], vla[N];
    vector<ar<int,2>>vs;

    for(int i = 0;i<N;i++){
        for(int j = 0;j<N;j++){
            q[j] = 0;
        }
        
        for(auto [to, pos] : vs){
            q[to] = pos;
        }

        // for(int j = 0;j<N;j++){
            // cout << q[j] << " ";
        // }
        // cout << " ";

        int a = tryCombination(q);
        // cout << a << "\n";

        if(a > i || a == -1){
            val[i] = 0;
        }
        else val[i] = 1;

        int l = 0, r = N - 1, ans = -1;
        while(l <= r){
            int mid = (l + r) / 2;

            for(int j = 0;j<=mid;j++){
                q[j] = val[i];
            }

            for(int j = mid + 1;j<N;j++){
                q[j] = (val[i] ^ 1);
            }

            for(auto [to, pos] : vs)
                q[to] = pos;

            a = tryCombination(q);
            // if(i == 2){
                // for(int j = 0;j<N;j++)cout << q[j] << " ";
                // cout << "\n";
                // cout << mid << " " << a  << " "  << val[i] << "\n";
            // }
            if(a > i || a == -1){
                r = mid - 1;
                ans = mid;
            }
            else l = mid + 1;
        }
        // cout << ans << "\n";
        vs.pb({ans, val[i]});
        vla[ans] = val[i];
        ps[ans] = i;
        // exit(0);
    }

    answer(vla, ps);



}

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