Submission #1313787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313787		Chinguun	동굴 (IOI13_cave)	C++20	0 / 100	126 ms	520 KiB

cave

#include "cave.h"

#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define pb push_back
#define ppb pop_back
#define meta int tm = (tl + tr) / 2, x = i * 2 + 1, y = x + 1

const int N = 5007;
const int TN = 4 * N;
const int oo = 1e9;
const int mod = 1e9 + 7;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;

const int NN = 5007;
int a[NN], n, ans1[NN], ans2[NN], k;
bool vis[NN];

int rev (int x) {
    if (x) return 0;
    return 1;
}

int rec (int l, int r, int p) {
    if (l == r) return l;

    int m = (l + r) / 2, re = rev(a[p]);

    for (int i = m + 1; i <= r; i++) 
        if (!vis[i]) a[i] = re;

    int c = tryCombination(a);

    if (c > p || c == -1) return rec (l, m, p);
    for (int i = m + 1; i <= r; i++) a[i] = k;
    return rec (m + 1, r, p);
}

void exploreCave(int N) {
    n = N;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) a[j] = 1;
        for (int j = 0; j < n; j++) {
            if (vis[j]) a[j] = ans1[j];
        }
        int b = tryCombination(a);
        if (b > i || b == -1) k = 1;
        else {
            k = 0;
            for (int j = 0; j < n; j++) 
                if (!vis[j]) a[i] = k;
        }
        
        int pos = rec(0, n - 1, i);
        ans2[pos] = i;
        ans1[pos] = k;
        a[pos] = k;
        vis[pos] = 1;
    }
    answer (ans1, ans2);
    return;
}

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