Submission #1166505

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166505		Boycl07	Cave (IOI13_cave)	C++20	100 / 100	609 ms	540 KiB

cave

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

using namespace std;

#define ll long long
#define rep(i, n) for(int i = 1; i <= (n); ++i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define forn(i, l, r) for(int i = (l); (i) <= (r); ++i)
#define ford(i, r, l) for(int i = (r); (i) >= (l); --i)
#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<double, double>
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a.size())
#define task "note"

template<typename T> bool maximize(T &res, const T &val) {if(res < val) {res = val; return 1;} return 0;}
template<typename T> bool minimize(T &res, const T &val) {if(res < val) return 0; res = val; return 1;}
inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}
const int N = 5000 + 3;
const int LOG = 12;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
double get_cur_time() {return chrono::steady_clock::now().time_since_epoch().count();}

int n;
int cur_S[N];
int cur_D[N];
int used[N];
void exploreCave(int N_)
{
    n = N_;
    int LG = __builtin_clz(n);
    REP(cur, n)
    {
        int state;
        REP(i, n) if(!used[i]) cur_S[i] = 1;
        state = tryCombination(cur_S);
        if(state == -1 || state > cur) state = 1;
        else state = 0;
        int pos = 0;
        for(int j = 0; j <= LOG; ++j)
        {
            REP(i, n) if(!used[i])
                cur_S[i] = !((i) >> j & 1) ^ state;
            int x = tryCombination(cur_S);
            if(x == -1 || x > cur) x = 1;
            else x = 0;
            pos |= x << j;
        }
        cur_S[pos] = state;
        cur_D[pos] = cur;
        used[pos] = 1;
    }
    answer(cur_S, cur_D);
}

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