제출 #566080

#제출 시각아이디문제언어결과실행 시간메모리
566080Leo121로봇 (IOI13_robots)C++14
0 / 100
1861 ms32484 KiB
#include <bits/stdc++.h> #include "robots.h" #define for0(i, n) for(int i = 0; i < int(n); ++ i) #define for1(i, n) for(int i = 1; i <= int(n); ++ i) #define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i) using namespace std; struct ura { int w, s, idx; }; struct ura2 { int pos, t; const bool operator < (const ura2 & a) const { return t < a.t; } }; const int maxn = 1e6; const int maxr = 5e4; int robot1[maxr]; int robot2[maxr]; ura peso[maxn]; ura tamanio[maxn]; bool usados[maxn]; int n, m, t; priority_queue<ura2> pq; bool ordena1 (ura a, ura b){ return a.w < b.w; } bool ordena2 (ura a, ura b) { return a.s < b.s; } void limpiar(){ while(!pq.empty()){ pq.pop(); } } bool probar(int aux){ memset(usados, 0, sizeof(usados)); int cant = 0; int idx = 0; limpiar(); for0(i, n){ forn(j, idx, t - 1){ if(peso[j].w < robot1[i]){ pq.push({peso[j].idx, peso[j].s}); idx ++; continue; } break; } cant += min((int) pq.size(), aux); int aux2 = (int) pq.size(); for0(i, min(aux2, aux)){ ura2 act = pq.top(); usados[act.pos] = 1; pq.pop(); } } limpiar(); idx = 0; for0(i, m){ forn(j, idx, t - 1){ if(tamanio[j].s < robot2[i]){ if(!usados[tamanio[j].idx]){ pq.push({tamanio[j].idx, tamanio[j].w}); } idx ++; continue; } break; } cant += min((int) pq.size(), aux); int aux2 = (int) pq.size(); for0(i, min(aux2, aux)){ ura2 act = pq.top(); usados[act.pos] = 1; pq.pop(); } } return (cant == t); } int bs(){ int li = 1, ls = t, mitad, res = 0; while(li <= ls){ mitad = (li + ls) / 2; if(probar(mitad)){ res = mitad; ls = mitad - 1; } else{ li = mitad + 1; } } return res; } int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) { n = A; m = B; for0(i, n){ robot1[i] = X[i]; } sort(robot1, robot1 + n); for0(i, m){ robot2[i] = Y[i]; } sort(robot2, robot2 + m); t = T; for0(i, t){ peso[i] = {W[i], S[i], i}; tamanio[i] = peso[i]; } sort(peso, peso + t, ordena1); sort(tamanio, tamanio + t, ordena2); return bs(); }
#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...