제출 #761474

#제출 시각아이디문제언어결과실행 시간메모리
761474nicksms로봇 (IOI13_robots)C++17
0 / 100
1 ms340 KiB
#include "robots.h" /** * Author: Nicholas Winschel * Created: 06.19.2023 14:12:26 **/ #include <bits/stdc++.h> using namespace std; using ll=long long; using db=long double; template<class T> using V=vector<T>; using vi = V<int>; using vl = V<ll>; using pi = pair<int,int>; #define f first #define s second #define sz(x) (int)((x).size()) const int MAXN = 1e6 + 5; const int MAXA = 5e4 + 5; bool rem[MAXN]; int inds[MAXN], inds2[MAXN]; int fi[MAXA]; int cur[MAXA]; int alo[MAXA]; int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) { sort(X, X+A); sort(Y, Y+B); iota(inds, inds+T, 0); iota(inds2, inds2+T, 0); sort(inds, inds+T, [&](int a, int b) {return W[a] < W[b];}); sort(inds2, inds2+T, [&](int a, int b) {return S[a] < S[b];}); int cp = 1; for (int i = 0; i < T; i++) while (cp <= A && X[cp-1] <= W[inds[i]]) fi[cp++]=i; for (int i = 0; i < A; i++) sort(inds+fi[i], inds+fi[i+1], [&](int a, int b) { return S[a] > S[b]; }); auto chk = [&](int d) -> bool { for (int i = 0; i < T; i++) rem[i]=true; for (int i = 0; i < A; i++) cur[i]=fi[i]; for (int i = 0; i < B; i++) alo[i]=d; using pr = pair<int, int>; priority_queue<pr> h; for (int i = 0; i < A; i++) { if (fi[i] < fi[i+1]) h.emplace(S[inds[fi[i]]], i); int k = d; while (sz(h) && k > 0) { k--; auto [x, y] = h.top(); h.pop(); rem[inds[cur[y]++]]=false; if (cur[y] < fi[y+1]) h.emplace(S[cur[y]], y); } } int p1 = 0, p2 = 0; while (p1 < B && p2 < T) { if (!rem[inds2[p2]]) { p2++; continue; } if (alo[p1]==0) { p1++; continue; } if (Y[p1] <= S[inds2[p2]]) { p1++; continue; } alo[p1]--,rem[inds2[p2]]=false; } return p2 == T; }; if (!chk(T)) return -1; int bl = -1,br=T; while (br - bl > 1) { int d = (br + bl) >> 1; if (chk(d)) br = d; else bl = d; } return br; }
#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...