Submission #468043

#	Time	Username	Problem	Language	Result	Execution time	Memory
468043		Karliver	동굴 (IOI13_cave)	C++14	100 / 100	391 ms	580 KiB

cave

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

#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;

const int INF = 1e9 + 1;
const int N = 2e5 + 100;
const double eps = 1e-7;

template <class T> using V = vector<T>;  
template <class T> using VV = V<V<T>>;  

template <typename XPAX>
void ckma(XPAX &x, XPAX y) {
    x = (x < y ? y : x);
}
template <typename XPAX>
void ckmi(XPAX &x, XPAX y) {
    x = (x > y ? y : x);
}



void exploreCave(int n) {
    /* ... */
    

    bool fin[n];

    int cur[n], st[n];
    int door[n];
    forn(i, n) {
        fin[i] = false;
        door[i] = -1;
        cur[i] = 0;
    }

    auto redo = [&]() {
        forn(i, n) if(!fin[i]) st[i] ^= 1;
    };

    forn(i, n) {
        forn(j, n) st[j] = cur[j];

        int mx = tryCombination(st);

        if(mx != i)
            redo();

        int l = 0, r =  n - 1;
        while(l < r) {
            int mid = (l + r) >> 1;
            for(int j = l;j <= mid;++j) {
                if(!fin[j]) st[j] ^= 1;
            }

            int x = tryCombination(st);

            if(x != i) {
                r = mid;
                for(int j = l;j <= mid;++j) {
                    if(!fin[j])st[j] ^= 1;
                }

            }
            else {
                l = mid + 1;
            }
        }
        fin[l] = 1;
        cur[l] = st[l] ^ 1;
        door[l] = i;
    }

    return answer(cur, door);





}

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