제출 #169538

#제출 시각아이디문제언어결과실행 시간메모리
169538Lawliet로봇 (IOI13_robots)C++14
100 / 100
2706 ms33900 KiB
#include "robots.h" #include <bits/stdc++.h> using namespace std; typedef pair<int,int> pii; const int MAXN = 1000010; int N; int qtdWeak; int qtdSmall; int sz[MAXN]; int weight[MAXN]; int sweepX[MAXN]; int sweepY[MAXN]; int szLimit[MAXN]; int weightLimit[MAXN]; bool picked[MAXN]; bool cmp(pii a, pii b) { int indA = a.second; int indB = b.second; if( a.first != b.first ) return a.first < b.first; return weight[indA] + sz[indA] < weight[indB] + sz[indB]; } bool cmpSz(int i, int j) { return sz[i] < sz[j]; } bool cmpWeight(int i, int j) { return weight[i] < weight[j]; } bool test(int k) { int p = 1; int qtdToys = 0; vector< int > aux; priority_queue< pii > s; memset( picked , false , sizeof(picked) ); for(int i = 1 ; i <= qtdSmall ; i++) { while( p <= N && sz[ sweepX[p] ] < szLimit[i] ) { int ind = sweepX[ p++ ]; s.push( { weight[ind] , ind } ); } for(int j = 0 ; j < k ; j++) { if( s.empty() ) break; int ind = s.top().second; qtdToys++; picked[ ind ] = true; s.pop(); } } p = 1; for(int i = 1 ; i <= qtdWeak ; i++) { while( p <= N && weight[ sweepY[p] ] < weightLimit[i] ) { int ind = sweepY[ p++ ]; if( picked[ind] ) continue; aux.push_back( ind ); } for(int j = 0 ; j < k ; j++) { if( aux.empty() ) break; qtdToys++; picked[ aux.back() ] = true; aux.pop_back(); } } return qtdToys == N; } int bs() { int l = 1; int r = N; if( !test( r ) ) return -1; while( l < r ) { int m = ( l + r )/2; if( test( m ) ) r = m; else l = m + 1; } return r; } int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) { N = T; qtdWeak = A; qtdSmall = B; for(int i = 1 ; i <= N ; i++) { sz[i] = S[i - 1]; weight[i] = W[i - 1]; sweepX[i] = sweepY[i] = i; } for(int i = 1 ; i <= qtdWeak ; i++) weightLimit[i] = X[i - 1]; for(int i = 1 ; i <= qtdSmall ; i++) szLimit[i] = Y[i - 1]; sort( sweepX + 1 , sweepX + N + 1 , cmpSz ); sort( sweepY + 1 , sweepY + N + 1 , cmpWeight ); sort( szLimit + 1 , szLimit + qtdSmall + 1 ); sort( weightLimit + 1 , weightLimit + qtdWeak + 1 ); 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...