oj.uz

Submission #518325

# Submission time Handle Problem Language Result Execution time Memory
518325 2022-01-23T11:27:01 Z Ai7081 Ball Machine (BOI13_ballmachine) C++17
16.1111 / 100
 170 ms 20744 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const bool debug = 0;

int n, q, p[N][20], op, x, fen[N], L, pos[N];
vector<int> adj[N], ord;
bool mark[N];

void add(int i, int val) {
    for (; i<=n; i+=i&(-i)) fen[i] += val;
    return;
}

int sum(int i) {
    int ret = 0;
    for (; i>0; i-=i&(-i)) ret += fen[i];
    return ret;
}

int find_first(int l, int r) {
    if (l == r) return l;
    int m = (l+r)/2;
    if (sum(m) == 0) return find_first(m+1, r);
    else return find_first(l, m);
}

void find_ord(int v) {
    for (int i=1; i<=L; i++) p[v][i] = p[p[v][i-1]][i-1];
    for (auto to : adj[v]) {
        find_ord(to);
    }
    ord.push_back(v);
    return;
}

pair<int, int> find_lift(int v) {
    int ti = 0;
    for (int i=L; i>=0; i--) {
        if (!mark[p[v][i]]) v = p[v][i], ti += pow(2, i);
    }
    return make_pair(v, ti);
}

int main() {
    scanf(" %d %d", &n, &q);
    L = ceil(log2(n + 1));
    for (int i=1; i<=n; i++) {
        scanf(" %d", &p[i][0]);
        adj[p[i][0]].push_back(i);
    }
    ord.push_back(0);
    find_ord(adj[0][0]);
    for (int i=1; i<=n; i++) pos[ord[i]] = i;

    if (debug) {
        printf("ord : ");
        for (auto it : ord) printf("%d ", it);
        printf("\npos : ");
        for (int i=0; i<=n; i++) printf("%d ", pos[i]);
        printf("\n");
        for (int i=1; i<=n; i++) {
            printf("lift %d : ", i);
            for (int j=0; j<=L; j++) printf("%d ", p[i][j]);
            printf("\n");
        }
    }

    mark[0] = true;
    for (int i=1; i<=n; i++) add(i, 1), mark[i] = true;
    while (q--) {
        scanf(" %d %d", &op, &x);
        if (op == 1) {
            int idx;
            for (int i=1; i<=x; i++) {
                idx = find_first(1, n);
                add(idx, -1);
                mark[ord[idx]] = false;
            }
            printf("%d\n", ord[idx]);
        }
        else {
            pair<int, int> p = find_lift(x);
            add(pos[p.first], 1);
            mark[p.first] = true;
            printf("%d\n", p.second);
        }

        if (debug) {
            printf("sum : ");
            for (int i=1; i<=n; i++) printf("%d ", sum(i));
            printf("\n");
        }
    }

    return 0;
}

/*
8 10
0
1
2
2
3
3
4
6
1 3
2 5
1 1


13 20
0
1
1
2
2
3
3
4
4
5
5
6
6

*/

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     scanf(" %d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
ballmachine.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         scanf(" %d", &p[i][0]);
      |         ~~~~~^~~~~~~~~~~~~~~~~
ballmachine.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         scanf(" %d %d", &op, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
ballmachine.cpp:80:35: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |             printf("%d\n", ord[idx]);
      |                                   ^

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Incorrect 98 ms 10588 KB Output isn't correct
3 Incorrect 62 ms 10660 KB Output isn't correct
4 Incorrect 2 ms 2636 KB Output isn't correct
5 Incorrect 2 ms 2636 KB Output isn't correct
6 Incorrect 2 ms 2764 KB Output isn't correct
7 Incorrect 2 ms 2660 KB Output isn't correct
8 Incorrect 3 ms 2764 KB Output isn't correct
9 Incorrect 7 ms 3148 KB Output isn't correct
10 Incorrect 19 ms 4732 KB Output isn't correct
11 Incorrect 79 ms 10652 KB Output isn't correct
12 Incorrect 58 ms 10820 KB Output isn't correct
13 Incorrect 73 ms 10568 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 6544 KB Output is correct
2 Incorrect 137 ms 17040 KB Output isn't correct
3 Incorrect 84 ms 14128 KB Output isn't correct
4 Incorrect 62 ms 7652 KB Output isn't correct
5 Incorrect 50 ms 7676 KB Output isn't correct
6 Incorrect 48 ms 7620 KB Output isn't correct
7 Incorrect 56 ms 6824 KB Output isn't correct
8 Correct 33 ms 6468 KB Output is correct
9 Incorrect 116 ms 17388 KB Output isn't correct
10 Incorrect 125 ms 16984 KB Output isn't correct
11 Incorrect 109 ms 16916 KB Output isn't correct
12 Incorrect 112 ms 15488 KB Output isn't correct
13 Correct 92 ms 18696 KB Output is correct
14 Incorrect 78 ms 14284 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 10192 KB Output isn't correct
2 Incorrect 131 ms 15884 KB Output isn't correct
3 Correct 102 ms 17248 KB Output is correct
4 Incorrect 95 ms 14668 KB Output isn't correct
5 Incorrect 103 ms 14276 KB Output isn't correct
6 Incorrect 114 ms 14292 KB Output isn't correct
7 Incorrect 90 ms 13428 KB Output isn't correct
8 Correct 99 ms 17168 KB Output is correct
9 Incorrect 134 ms 17484 KB Output isn't correct
10 Incorrect 170 ms 17144 KB Output isn't correct
11 Incorrect 168 ms 17140 KB Output isn't correct
12 Incorrect 134 ms 15764 KB Output isn't correct
13 Correct 160 ms 20744 KB Output is correct
14 Incorrect 96 ms 14124 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 124 ms 17268 KB Output isn't correct
2 Incorrect 131 ms 15660 KB Output isn't correct
3 Correct 100 ms 20436 KB Output is correct
4 Incorrect 131 ms 17396 KB Output isn't correct
5 Incorrect 121 ms 16828 KB Output isn't correct
6 Incorrect 106 ms 16744 KB Output isn't correct
7 Incorrect 126 ms 15604 KB Output isn't correct
8 Correct 99 ms 20468 KB Output is correct
9 Incorrect 83 ms 13952 KB Output isn't correct