oj.uz

Submission #959970

# Submission time Handle Problem Language Result Execution time Memory
959970 2024-04-09T11:27:44 Z hqminhuwu Cave (IOI13_cave) C++14
12 / 100
 178 ms 10324 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){
            if (i <= mid)
                a[i] = u;
            else a[i] = 1 - u;
        }
        if (get() < x){
            forr (i, l, r)
            if (flag[i] == -1){
                if (i <= mid)
                    a[i] = 1 - u;
                else a[i] = 1;
            }
            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 109 ms 10164 KB Output is correct
2 Correct 112 ms 10160 KB Output is correct
3 Correct 166 ms 10068 KB Output is correct
4 Correct 123 ms 10176 KB Output is correct
5 Correct 174 ms 10164 KB Output is correct
6 Correct 163 ms 10068 KB Output is correct
7 Correct 172 ms 10068 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 2 ms 10076 KB Output is correct
12 Correct 169 ms 10324 KB Output is correct
13 Correct 163 ms 10168 KB Output is correct
14 Correct 163 ms 10168 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 10064 KB Output is correct
2 Correct 2 ms 10076 KB Output is correct
3 Correct 166 ms 10184 KB Output is correct
4 Correct 3 ms 10076 KB Output is correct
5 Correct 2 ms 10072 KB Output is correct
6 Incorrect 178 ms 10168 KB Answer is wrong
7 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 Correct 2 ms 10076 KB Output is correct
4 Correct 2 ms 10076 KB Output is correct
5 Incorrect 2 ms 10076 KB Answer is wrong
6 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 Correct 2 ms 10076 KB Output is correct
4 Correct 2 ms 10076 KB Output is correct
5 Incorrect 2 ms 10076 KB Answer is wrong
6 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 10164 KB Output is correct
2 Correct 112 ms 10160 KB Output is correct
3 Correct 166 ms 10068 KB Output is correct
4 Correct 123 ms 10176 KB Output is correct
5 Correct 174 ms 10164 KB Output is correct
6 Correct 163 ms 10068 KB Output is correct
7 Correct 172 ms 10068 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 2 ms 10076 KB Output is correct
12 Correct 169 ms 10324 KB Output is correct
13 Correct 163 ms 10168 KB Output is correct
14 Correct 163 ms 10168 KB Output is correct
15 Correct 173 ms 10064 KB Output is correct
16 Correct 2 ms 10076 KB Output is correct
17 Correct 166 ms 10184 KB Output is correct
18 Correct 3 ms 10076 KB Output is correct
19 Correct 2 ms 10072 KB Output is correct
20 Incorrect 178 ms 10168 KB Answer is wrong
21 Halted 0 ms 0 KB -