Submission #1236966

#TimeUsernameProblemLanguageResultExecution timeMemory
1236966nerrrminRobots (IOI13_robots)C++20
76 / 100
3092 ms42128 KiB
#include "robots.h" #include<iostream> #include<queue> #include<vector> #include<algorithm> #define pb push_back using namespace std; const long long maxn = 1e6 + 10; long long a, b, t; long long x[maxn], y[maxn]; long long w[maxn], s[maxn]; struct robot { long long w, s, i; robot(){}; robot(long long _w, long long _s, long long _i) { w = _w; s = _s; i = _i; } }; bool cmp(robot a, robot b) { return (a.w < b.w); } vector < robot > g; long long mark[maxn]; bool check(long long mid) { for (long long i = 0; i < t; ++ i) mark[i] = 0; long long j = 0; priority_queue < pair < long long, long long > > q; for (long long i = 0; i < a; ++ i) { while(j < g.size() && g[j].w < x[i]) { long long rs = g[j].s; long long ri = g[j].i; q.push({rs, ri}); j ++; } long long turn = mid; while(turn -- && q.size()) { long long ww = q.top().second; // cout << "del " << q.top().first << " " << w[q.top().second] << endl; q.pop(); mark[ww] = 1; } } vector < pair < long long, long long > > u; for (long long i = 0; i < t; ++ i) { if(mark[i]) { //cout << "we marked something " << i << endl; continue; } // cout << "left for small " << s[i] << " " << i << endl; u.pb({s[i], i}); } sort(u.begin(), u.end()); j = 0; for (long long i = 0; i < b; ++ i) { long long turn = mid; while(j < u.size() && u[j].first < y[i] && turn) { long long ri = u[j].second; mark[ri] = 1; j ++; turn --; } } for (long long i = 0; i < t; ++ i) if(!mark[i]) { // cout << i; return false; } return true; } int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) { a = A; b = B; t = T; for (long long i = 0; i < a; ++ i) x[i] = X[i]; for (long long i = 0; i < b; ++ i) y[i] = Y[i]; for (long long i = 0; i < t; ++ i) { w[i] = W[i]; s[i] = S[i]; g.pb(robot(w[i], s[i], i)); } sort(x, x+a); sort(y, y+b); sort(g.begin(), g.end(), cmp); long long l = 0, r = 1e13, mid, ans = 1e13; while(l <= r) { mid = (l + r)/2; if(check(mid)) { ans = mid; r = mid - 1; } else l = mid + 1; } if(ans == 1e13)return -1; else return ans; }
#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...