제출 #518323

#제출 시각아이디문제언어결과실행 시간메모리
518323Ai7081Ball Machine (BOI13_ballmachine)C++17
0 / 100
140 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]) { 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 */

컴파일 시 표준 에러 (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: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);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...