제출 #404697

#제출 시각아이디문제언어결과실행 시간메모리
404697Kenzo_1114로봇 (IOI13_robots)C++17
0 / 100
4 ms332 KiB
#include<bits/stdc++.h> #include "robots.h" using namespace std; const int MAXN = 100010; const int MAXT = 1000010; int a, b, n, x[MAXN], y[MAXN], w[MAXT], s[MAXT]; bool valid(int mns) { vector<pair<int, int> > p; for(int i = 0; i < n; i++) p.push_back({w[i], i}); sort(p.begin(), p.end()); int id = 0; set<pair<int, int> > xs, ys; set<pair<int, int> > :: iterator it; for(int i = 0; i < (int) p.size(); i++) { int xcur = p[i].first; int j = p[i].second; int ycur = s[j]; while(id < a && xcur > x[id]) { for(int k = 0; k < mns; k++) if(!ys.empty()) ys.erase(*(--ys.end())); id++; } ys.insert({ycur, j}); } while(id < a) { for(int k = 0; k < mns; k++) if(!ys.empty()) ys.erase(*(--ys.end())); id++; } p.clear(); for(it = ys.begin(); it != ys.end(); it++) p.push_back(*it); id = 0; for(int i = 0; i < (int) p.size(); i++) { int ycur = p[i].first; int j = p[i].second; int xcur = w[j]; while(id < b && ycur > y[id]) { for(int k = 0; k < mns; k++) if(!xs.empty()) xs.erase(*(--xs.end())); id++; } xs.insert({xcur, j}); } while(id < b) { for(int k = 0; k < mns; k++) if(!xs.empty()) xs.erase(*(--xs.end())); id++; } if(xs.empty()) return true; return false; } int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) { a = A, b = B, n = T; for(int i = 0; i < A; i++) x[i] = X[i]; for(int i = 0; i < B; i++) y[i] = Y[i]; for(int i = 0; i < T; i++) w[i] = W[i], s[i] = S[i]; sort(x, x + A); sort(y, y + B); int bg = 0, ed = MAXT; while(bg < ed) { int mid = (bg == ed - 1) ? bg : (bg + ed) >> 1; if(valid(mid)) ed = mid; else bg = mid + 1; } return (bg == MAXT) ? -1 : bg; }
#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...