제출 #518303

#제출 시각아이디문제언어결과실행 시간메모리
518303Ai7081Ball Machine (BOI13_ballmachine)C++17
0 / 100
149 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); L = ceil(log2(n+.0)); 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) { cout << "ord "; for (auto it : ord) cout << it << ' '; cout << endl; for (int i=1; i<=n; i++) { cout << "b lift " << i << " : "; for (int j=0; j<=L; j++) cout << p[i][j] << ' '; cout << endl; } } 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; if (debug) { cout << "fill " << i << " at: " << ord[idx] << endl; } } 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) { for (int i=1; i<=n; i++) { cout << sum(i) << ' '; } cout << endl; } } return 0; } /* 8 10 0 1 2 2 3 3 4 6 1 3 2 5 1 1 */

컴파일 시 표준 에러 (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 | }
      | ^
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     scanf(" %d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
ballmachine.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         scanf(" %d", &p[i][0]);
      |         ~~~~~^~~~~~~~~~~~~~~~~
ballmachine.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         scanf(" %d %d", &op, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...