Submission #1077968

#TimeUsernameProblemLanguageResultExecution timeMemory
1077968TheQuantiXRobots (IOI13_robots)C++17
76 / 100
3092 ms39552 KiB
#include <bits/stdc++.h> #include "robots.h" using namespace std; using ll = long long; ll n, m, q, k, x, y, a, b, c; int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) { ll l = 0, r = T + 1; vector< pair<ll, ll> > v; for (int i = 0; i < T; i++) { v.push_back({W[i], S[i]}); } sort(X, X + A); sort(Y, Y + B); sort(v.begin(), v.end()); while (r > l) { ll mid = (r + l) / 2; // cout << mid << endl; ll pos = 0; multiset<ll> st; for (int i = 0; i < A; i++) { while (pos != T && v[pos].first < X[i]) { st.insert(v[pos].second); pos++; } for (int j = 0; j < mid; j++) { if (st.size() == 0) { break; } // cout << i << ' ' << *st.rbegin() << endl; st.erase(--st.end()); } } while (pos != T) { st.insert(v[pos].second); pos++; } // cout << st.size() << endl; bool fl = 1; for (int i = B - 1; i >= 0; i--) { if (st.empty()) { break; } if ((*st.rbegin()) >= Y[i]) { fl = 0; break; } for (int j = 0; j < mid; j++) { if (st.size() == 0) { break; } st.erase(--st.end()); } } if (st.size() != 0) { fl = 0; } if (fl) { r = mid; } else { l = mid + 1; } } if (l == T + 1) { return -1; } return l; }
#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...