제출 #761484

#제출 시각아이디문제언어결과실행 시간메모리
761484nicksms로봇 (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[]) { if (A) sort(X, X+A); if (B) 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; if (W[inds[T-1]] < X[A-1]) fi[A]=T; 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 { // cerr << "call " << d << endl; 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; int cnt = 0; 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(); cnt++; // cerr << "mch " << inds[cur[y]] << " to rob " << i << endl; rem[inds[cur[y]++]]=false; if (cur[y] < fi[y+1]) h.emplace(S[inds[cur[y]]], y); } } if (cnt == T) return true; int p1 = 0, p2 = 0; while (p1 < B && p2 < T) { if (!rem[inds2[p2]]) { // cerr << "skip " << inds2[p2] << endl; 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...