제출 #433118

#제출 시각아이디문제언어결과실행 시간메모리
433118rainboyArchery (IOI09_archery)C11
7 / 100
376 ms6228 KiB
#include <stdio.h> #define N 200000 #define N_ (1 << 18) /* N_ = pow2(ceil(log2(N))) */ int min(int a, int b) { return a < b ? a : b; } int pref[N_ * 2], sum[N_ * 2], n_; void pul(int i) { int l = i << 1, r = l | 1; pref[i] = min(pref[l], sum[l] + pref[r]); sum[i] = sum[l] + sum[r]; } void build(int n) { int i; n_ = 1; while (n_ < n) n_ <<= 1; for (i = 0; i < n_; i++) if (i < n) sum[n_ + i] = pref[n_ + i] = -1; for (i = n_ - 1; i > 0; i--) pul(i); } int kk[N]; void update(int i, int x) { i += n_; pref[i] = sum[i] += x; while (i > 1) pul(i >>= 1); } int query(int i) { int l, r, x; x = 0; for (l = n_ + i, r = n_ + n_ - 1; l <= r; l >>= 1, r >>= 1) if ((l & 1) == 1) { if (x + pref[l] <= 0) { i = l; while (i < n_) if (x + pref[i << 1 | 0] <= 0) i = i << 1 | 0; else x += sum[i << 1 | 0], i = i << 1 | 1; return i - n_; } l++; } if (x + pref[1] <= 0) return -1; i = 1; while (i < n_) if (x + pref[i << 1 | 0] <= 0) i = i << 1 | 0; else x += sum[i << 1 | 0], i = i << 1 | 1; return i - n_; } int add(int i) { update(i, 1), kk[i]++; return query(i); } int delete(int i) { int j = query(i); update(i, -1), kk[i]--; return j; } int main() { static int aa[N * 2]; int n, r, p, p_, i, i_, a_, mn; scanf("%d%d", &n, &r); for (i = 0; i < n * 2; i++) scanf("%d", &aa[i]), aa[i]--; build(n); a_ = aa[0]; if (a_ == 0) i_ = n - 1; else if (a_ > n) { add(n - 1 - 0); for (i = 0; i < n * 2; i++) if (aa[i] > a_) add(n - 1 - (i / 2)); p_ = n, i_ = -1; for (i = 0; i < n; i++) { if (i > 0) { if (aa[i * 2] > a_) delete(n - 1 - i), add(n - 1 - (i - 1)); aa[(i - 1) * 2] = aa[i * 2], aa[i * 2] = a_; } p = n - 1 - add(n - 1 - i), delete(n - 1 - i); if (p_ >= p) p_ = p, i_ = i; } } else { for (i = 0; i < n * 2; i++) if (aa[i] < a_) add(i / 2); mn = 0; while (kk[mn] == 0) mn++; p_ = n, i_ = -1; for (i = 0; i < n; i++) { if (i > 0) { if (aa[i * 2] < a_) { delete(i), add(i - 1); if (mn == i) mn--; } aa[(i - 1) * 2] = aa[i * 2], aa[i * 2] = a_; } if (i < mn) { p = delete(mn); if (kk[mn] > 0) p ^= delete(mn), p ^= add((mn + 1) % n), delete((mn + 1) % n), add(mn); add(mn); } else if (i > mn) { p = delete(mn); if (kk[mn] > 0) p ^= delete(mn), p ^= add((mn + 1) % n), delete((mn + 1) % n), add(mn); p ^= add(i), delete(i); add(mn); } else p = add((i + 1) % n), delete((i + 1) % n); p = (p - r % n + n) % n; if (p_ >= p) p_ = p, i_ = i; } } printf("%d\n", i_ + 1); return 0; }

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

archery.c: In function 'main':
archery.c:83:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |  scanf("%d%d", &n, &r);
      |  ^~~~~~~~~~~~~~~~~~~~~
archery.c:85:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   scanf("%d", &aa[i]), aa[i]--;
      |   ^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...