Submission #1185843

#TimeUsernameProblemLanguageResultExecution timeMemory
1185843harvsftwRobots (IOI13_robots)C++20
90 / 100
3097 ms67340 KiB
#pragma GCC optimize("O3,inline") #include <bits/stdc++.h> #include "robots.h" using namespace std; #define F(i, n) for(int i = 0; i < (n); i++) int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) { using state = tuple<int, int, int>; sort(X, X + A); sort(Y, Y + B); set<state> by_weight; F(i, T) { by_weight.emplace(W[i], S[i], i); //by_size.emplace(S[i], W[i], i); } auto solver = [&](int num_per_robot) { priority_queue<pair<int, int>> pq; vector<bool> taken; auto it = by_weight.begin(); F(i, A) { int robot_weight_limit = X[i]; while(it != by_weight.end() && get<0>(*it) < robot_weight_limit) { pq.emplace(get<1>(*it), get<2>(*it)); ++it; } int cnt = num_per_robot; while(!pq.empty() && cnt > 0) { auto [sz, idx] = pq.top(); pq.pop(); cnt--; } } set<pair<int, int>> by_size; while(!pq.empty()) { auto [_, idx] = pq.top(); pq.pop(); by_size.emplace(S[idx], idx); } while(it != by_weight.end()) { by_size.emplace(get<1>(*it), get<2>(*it)); ++it; } auto it2 = by_size.empty() ? by_size.end() : by_size.begin(); priority_queue<pair<int, int>> pq2; F(i, B) { int robot_size_limit = Y[i]; while(it2 != by_size.end() && it2->first < robot_size_limit) { pq2.push(*it2); ++it2; } int cnt = num_per_robot; while(!pq2.empty() && cnt > 0) { auto [sz, idx] = pq2.top(); pq2.pop(); cnt--; } } //cout << num_per_robot << " solver return " << (pq2.empty()) << " " << (it2 == by_size.end()) << " " << by_size.size() << endl; return pq2.empty() && it2 == by_size.end(); }; int l = 1, r = T; while(l <= r) { int m = (l + r) / 2; if(solver(m)) { r = m - 1; } else { l = m + 1; } } if(!solver(l)) { 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...