제출 #308877

#제출 시각아이디문제언어결과실행 시간메모리
308877kylych03로봇 (IOI13_robots)C++14
90 / 100
3086 ms55544 KiB
#include "robots.h" //#include "grader.cpp" #include <bits/stdc++.h> using namespace std; vector <pair <int,int> > toy; int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) { sort(X, X+A); sort(Y, Y+B); if(A==0){ swap(X,Y); swap(W,S); swap(A,B); } toy.resize(T); for(int i = 0 ; i < T ; i++){ toy[i].first = W[i]; toy[i].second = S[i]; if(W[i]>= X[A-1] && S[i]>=Y[B-1]) return -1; } sort(toy.begin(), toy.end() ); if(B==0){ if(X[A-1] <= toy[T-1].first ) return -1; int res = (T + A -1 )/ A; for(int i = 0; i < A - 1 ;i++){ if( X[i] <= toy[0].first){ res = max ( res, (T + ( A - i- 1) -1 )/ (A - i -1 )); } int ind = upper_bound(toy.begin(), toy.end(), make_pair (X[i], 2000000002)) - toy.begin() ; res = max ( res, (T - ind + (A-i-1) - 1) / ( A - i - 1)); } return res; } int l = 1, r = T; int ans = T; while(r - l > 0){ int mid = (l + r) / 2; multiset <int > vec, vec1; multiset <int > ::iterator it; int cnt = 0; for(int i = 0 ; i < A ; i++){ int sz = 0; while( cnt < T && X[i] > toy[cnt].first){ vec.insert(-toy[cnt].second); cnt++; } while(vec.size()> 0 && sz<mid){ vec.erase(vec.begin()); sz++; } if(i==A-1){ while(cnt < T){ vec.insert(-toy[cnt].second); cnt++; } } } for(it = vec.begin(); it!=vec.end(); it++){ int x = *it; vec1.insert(-x); } for(int i = 0 ; i < B; i++){ int sz =0; while(vec1.size()> 0 && sz < mid && *vec1.begin()< Y[i] ){ vec1.erase(vec1.begin()); sz++; } } if(vec1.size()==0 ){ r = mid; ans = mid; } else{ l = mid + 1; } } return ans; } /* 3 2 10 6 2 9 4 7 4 6 8 5 2 3 7 9 1 8 5 1 3 3 8 7 7 6 10 5 */
#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...