제출 #518315

#제출 시각아이디문제언어결과실행 시간메모리
518315Ai7081Ball Machine (BOI13_ballmachine)C++17
0 / 100
166 ms131076 KiB
#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) find_first(m+1, r); else 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]) { if (to == p[v][0]) continue; 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); ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> q; L = ceil(log2(n+.0)); for (int i=1; i<=n; i++) { //scanf(" %d", &p[i][0]); cin >> 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); cin >> 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]); cout << ord[idx] << "\n"; } else { pair<int, int> p = find_lift(x); add(pos[p.first], 1); mark[p.first] = true; //printf("%d\n", p.second); cout << p.second << "\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 */

컴파일 시 표준 에러 (stderr) 메시지

ballmachine.cpp: In function 'int find_first(int, int)':
ballmachine.cpp:26:1: warning: control reaches end of non-void function [-Wreturn-type]
   26 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...