Submission #959964

# Submission time Handle Problem Language Result Execution time Memory
959964 2024-04-09T11:22:22 Z hqminhuwu Cave (IOI13_cave) C++14
12 / 100
202 ms 10188 KB
#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;

#define forr(_a,_b,_c) for(int _a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

const int maxn = 5e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7; // 998244353;

int flag[maxn], state[maxn], a[maxn], n, ansS[maxn], ansD[maxn];

int get (){
    int tmp = tryCombination(a);
    if (tmp < 0) return oo;
    return tmp - 1;
}

void solve (int x){
    forf (i, 0, n){
        if (flag[i] != -1)
            a[i] = state[i];
        else a[i] = 0;
    }

    int f = get();
    int u = (f < x);

    int l = 0, r = n - 1;
    while (l < r){
        int mid = (l + r) >> 1;
        forr (i, l, r)
        if (flag[i] == -1)
            a[i] = (i > mid) ^ u;
        if (get() < x){
            forr (i, l, r)
            if (flag[i] == -1)
                a[i] = (i <= mid) ^ u;
            l = mid + 1;
        } 
        else r = mid;
    }

    state[l] = u;
    flag[l] = x;
}

void exploreCave (int num){
    n = num;
    memset (flag, -1, sizeof flag);

    forf (i, 0, n)
        solve(i);
    forf (i, 0, n){
        ansS[flag[i]] = state[i];
        ansD[flag[i]] = i;
    }
    answer(ansS, ansD);
}

# Verdict Execution time Memory Grader output
1 Correct 115 ms 10132 KB Output is correct
2 Correct 129 ms 10068 KB Output is correct
3 Correct 174 ms 10132 KB Output is correct
4 Correct 137 ms 10132 KB Output is correct
5 Correct 182 ms 10128 KB Output is correct
6 Correct 172 ms 10144 KB Output is correct
7 Correct 202 ms 10148 KB Output is correct
8 Correct 2 ms 10076 KB Output is correct
9 Correct 2 ms 10076 KB Output is correct
10 Correct 2 ms 10076 KB Output is correct
11 Correct 3 ms 10072 KB Output is correct
12 Correct 175 ms 10128 KB Output is correct
13 Correct 174 ms 10068 KB Output is correct
14 Correct 172 ms 10128 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 189 ms 10068 KB Output is correct
2 Correct 2 ms 10076 KB Output is correct
3 Correct 201 ms 10132 KB Output is correct
4 Correct 3 ms 10072 KB Output is correct
5 Correct 3 ms 10076 KB Output is correct
6 Incorrect 179 ms 10188 KB Answer is wrong
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 10072 KB Output is correct
2 Correct 2 ms 10076 KB Output is correct
3 Correct 2 ms 10076 KB Output is correct
4 Correct 2 ms 10072 KB Output is correct
5 Incorrect 2 ms 10076 KB Answer is wrong
6 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 10072 KB Output is correct
2 Correct 2 ms 10076 KB Output is correct
3 Correct 2 ms 10076 KB Output is correct
4 Correct 2 ms 10072 KB Output is correct
5 Incorrect 2 ms 10076 KB Answer is wrong
6 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 115 ms 10132 KB Output is correct
2 Correct 129 ms 10068 KB Output is correct
3 Correct 174 ms 10132 KB Output is correct
4 Correct 137 ms 10132 KB Output is correct
5 Correct 182 ms 10128 KB Output is correct
6 Correct 172 ms 10144 KB Output is correct
7 Correct 202 ms 10148 KB Output is correct
8 Correct 2 ms 10076 KB Output is correct
9 Correct 2 ms 10076 KB Output is correct
10 Correct 2 ms 10076 KB Output is correct
11 Correct 3 ms 10072 KB Output is correct
12 Correct 175 ms 10128 KB Output is correct
13 Correct 174 ms 10068 KB Output is correct
14 Correct 172 ms 10128 KB Output is correct
15 Correct 189 ms 10068 KB Output is correct
16 Correct 2 ms 10076 KB Output is correct
17 Correct 201 ms 10132 KB Output is correct
18 Correct 3 ms 10072 KB Output is correct
19 Correct 3 ms 10076 KB Output is correct
20 Incorrect 179 ms 10188 KB Answer is wrong
21 Halted 0 ms 0 KB -