Submission #127504

#	Time	Username	Problem	Language	Result	Execution time	Memory
127504		MoNsTeR_CuBe	Robots (IOI13_robots)	C++17	100 / 100	2951 ms	48440 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
 
using namespace std;
 
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
   #define int long long 
   sort(X,X+A);
   sort(Y,Y+B);
   
   for(int i = 0; i < T; i++){
		if(W[i] >= X[A-1] && S[i] >= Y[B-1]){
			return -1;
		}
   }
   
   vector< pair<int, int> > L;
   
   for(int i = 0; i < T; i++){
		L.push_back(make_pair(W[i], S[i]));
   }
   
   sort(L.begin(), L.end());
   
   //for(auto p : L) cout << p.first << ' ' << p.second << endl;
   
   int left = 1, right = T;
   
   while(left < right){
		int mid = (left+right)/2;
		
		priority_queue< pair<int, int> > pq;
		
		int curr = 0;
		
		for(int i = 0; i < A; i++){
			while(curr < T && L[curr].first < X[i]){
				swap(L[curr].first, L[curr].second);
				pq.push(L[curr]);
				swap(L[curr].first, L[curr].second);
				curr++;
			}
			int rem = mid;
			while(!pq.empty() && rem){
				pq.pop();
				rem--;
			}
		}
		
		vector< pair<int, int> > remaining;
		
		for(int i = curr; i < T; i++){
			remaining.push_back(L[i]);
			swap(remaining.back().first, remaining.back().second);
		}
		
		while(!pq.empty()){
			remaining.push_back(pq.top());
			pq.pop();
		}
		
		sort(remaining.begin(), remaining.end());
		////////////////////////////////////////////////////////////////////////
		//cout << "Size " << remaining.size() << ' ' << mid << endl;
		//for(auto p : remaining) cout << p.first << ' ' << p.second << endl;
		curr = 0;
		for(int i = 0; i < B; i++){
			while(curr < (int)remaining.size() && remaining[curr].first < Y[i]){
				pq.push(remaining[curr]);
				curr++;
			}
			int rem = mid;
			while(!pq.empty() && rem){
				pq.pop();
				rem--;
			}
		}
		
		if(pq.empty() && curr == (int)remaining.size()){
			right = mid;
		}else{
			left = mid+1;
		}
   }
   
   return right;
   #undef int
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 10 / 10