oj.uz

Submission #959961

# Submission time Handle Problem Language Result Execution time Memory
959961 2024-04-09T11:19:08 Z hqminhuwu Cave (IOI13_cave) C++14
12 / 100
 212 ms 10172 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){
    forr (i, 1, 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);
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 10148 KB Output is correct
2 Correct 126 ms 10068 KB Output is correct
3 Correct 212 ms 10168 KB Output is correct
4 Correct 126 ms 10064 KB Output is correct
5 Correct 192 ms 10068 KB Output is correct
6 Correct 175 ms 10168 KB Output is correct
7 Correct 183 ms 10064 KB Output is correct
8 Correct 2 ms 9912 KB Output is correct
9 Correct 2 ms 10076 KB Output is correct
10 Correct 2 ms 10076 KB Output is correct
11 Correct 2 ms 10076 KB Output is correct
12 Correct 203 ms 10164 KB Output is correct
13 Correct 173 ms 10168 KB Output is correct
14 Correct 172 ms 10172 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 10068 KB Output is correct
2 Correct 2 ms 10076 KB Output is correct
3 Correct 171 ms 10132 KB Output is correct
4 Incorrect 2 ms 10072 KB Answer is wrong
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10076 KB Output is correct
2 Correct 2 ms 10076 KB Output is correct
3 Incorrect 2 ms 10076 KB Answer is wrong
4 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10076 KB Output is correct
2 Correct 2 ms 10076 KB Output is correct
3 Incorrect 2 ms 10076 KB Answer is wrong
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 10148 KB Output is correct
2 Correct 126 ms 10068 KB Output is correct
3 Correct 212 ms 10168 KB Output is correct
4 Correct 126 ms 10064 KB Output is correct
5 Correct 192 ms 10068 KB Output is correct
6 Correct 175 ms 10168 KB Output is correct
7 Correct 183 ms 10064 KB Output is correct
8 Correct 2 ms 9912 KB Output is correct
9 Correct 2 ms 10076 KB Output is correct
10 Correct 2 ms 10076 KB Output is correct
11 Correct 2 ms 10076 KB Output is correct
12 Correct 203 ms 10164 KB Output is correct
13 Correct 173 ms 10168 KB Output is correct
14 Correct 172 ms 10172 KB Output is correct
15 Correct 182 ms 10068 KB Output is correct
16 Correct 2 ms 10076 KB Output is correct
17 Correct 171 ms 10132 KB Output is correct
18 Incorrect 2 ms 10072 KB Answer is wrong
19 Halted 0 ms 0 KB -