제출 #944390

#제출 시각아이디문제언어결과실행 시간메모리
944390wii로봇 (IOI13_robots)C++17
0 / 100
3 ms5980 KiB
#include "robots.h" #include <bits/stdc++.h> using namespace std; const int MaxN = 5e4 + 5; int cnt[MaxN], jump[MaxN]; priority_queue<int, vector<int>, greater<int>> q[MaxN]; struct comp { bool operator() (int x, int y) const { if (q[x].size() == q[y].size()) return x < y; return q[x].size() > q[y].size(); } }; int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) { bool impossible = false; function<void(int)> pushSize = [&](int s) { int id = upper_bound(Y, Y + A, s) - Y; if (id < B) cnt[id] += 1; else impossible = true; }; function<void(int, int)> pushWeight = [&](int w, int s) { int id = upper_bound(X, X + A, w) - X; if (id < A) q[id].push(s); else pushSize(s); }; function<int(int, int)> movetoTop = [&](int u, int top) { if (u >= A) return u; if (q[u].size() > top) return jump[u] = movetoTop(jump[u], top); else return u; }; function<void(int)> balance = [&](int lim) { for (int i = 0; i < B; ++i) { if (cnt[i] > lim) cnt[i + 1] += cnt[i] - lim, cnt[i] = lim; } if (cnt[B] > lim) impossible = true; }; function<bool(int)> check = [&](int lim) { int remain = 0; for (int i = 0; i < B; ++i) { remain = (cnt[i] + remain > lim) ? cnt[i] + remain - lim : 0; } return remain == 0; }; function<int()> auto_balanced = [&]() { int l = 0, r = T; while (l <= r) { int mid = (l + r) >> 1; if (check(mid)) r = mid - 1; else l = mid + 1; } balance(r + 1); return r + 1; }; sort(X, X + A); sort(Y, Y + B); for (int i = 0; i < A; ++i) jump[i] = i + 1; for (int i = 0; i < T; ++i) { pushWeight(W[i], S[i]); } if (impossible) return -1; cout << "???" << endl; set<int, comp> s; for (int i = 0; i < A; ++i) if (q[i].size()) s.insert(i); int lst = -1; while (!s.empty()) { int u = *s.begin(); s.erase(s.begin()); int v = movetoTop(u, q[u].size() - 1); if (lst != q[u].size()) { balance(q[u].size() - 1); if (impossible) return q[u].size(); } lst = q[u].size(); int Size = q[u].top(); q[u].pop(); if (v < A) { s.erase(v); q[v].push(Size); s.insert(v); } else { pushSize(Size); } if (!q[u].empty()) s.insert(u); } //return 1; return auto_balanced(); }

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

robots.cpp: In lambda function:
robots.cpp:40:25: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |         if (q[u].size() > top)
      |             ~~~~~~~~~~~~^~~~~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:100:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         if (lst != q[u].size()) {
      |             ~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...