Submission #144582

#	Time	Username	Problem	Language	Result	Execution time	Memory
144582		youssefbou62	Robots (IOI13_robots)	C++14	100 / 100	2685 ms	32896 KiB

robots

#include  <bits/stdc++.h>
#include "robots.h"
using namespace std;

#define mp make_pair
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define allarr(a) a , a + n
#define ll long long
#define ull unsigned long long 
#define pb push_back
#define fastio ios_base::sync_with_stdio(false) ; cin.tie(NULL); cout.tie(NULL)
typedef pair<int, int> pi;
typedef pair<ll,ll> pll; 
typedef pair<int,pi> trp ;
typedef vector<pi> vpi;
typedef vector<pll> vpll ;
// int ab  (int  x ) { return (x>0?x:-x); }
const int TT = 1e6+5; 
bool done[TT]; 


struct Toy
{
	int w , s , ind; 
};

bool comW(Toy a , Toy b){
	return (a.w < b.w); 
}
bool comS(Toy a , Toy b){
	return (a.s < b.s); 
}
int putaway(int A, int B, int T,int X[], int Y[], int W[], int S[]){
	int l = 0 , r = T; 
	sort(X,X+A); 
	sort(Y,Y+B); 
	vector<Toy> ByWei(T),BySi(T); 
	for(int i = 0 ; i < T ; i++ ){
		// ByWei.pb({W[i],S[i],i}); 
		// BySi.pb({S[i],W[i],i});
		ByWei[i].w=BySi[i].w = W[i]; 
		BySi[i].s = ByWei[i].s = S[i];  
		BySi[i].ind = ByWei[i].ind = i ; 
		// BySi[i]={S[i],W[i],i};  
	}
	sort(all(ByWei),comW); 
	sort(all(BySi),comS); 
	int ans = -1 ; 
	priority_queue<pi> q;
	 pi p;
	 int mins,i;
	 int DONE; 
	while ( l <= r ){
		DONE = 0 ; 
		int mid = l + (r-l)/2;
		for( i = 0 ; i < T ; i++ )done[i]=0; 
		// memset(done,0,sizeof done); 
		 i = 0 ; 
		// q = priority_queue<pi> () ; 
		for(int a=0;a<A;a++){
			while(i < T && ByWei[i].w<X[a]){
				if( !done[ByWei[i].ind])
					q.push({ByWei[i].s,ByWei[i].ind}); 
				i++; 
			}
			 mins = mid;
			while(mins&&!q.empty()){
				p = q.top(); 
				q.pop();
				assert(!done[p.se]); 
				done[p.se]=1; 
				mins--;
				DONE ++ ;   
			}
		}
		while(!q.empty())q.pop();  
		i =0;
		// q = priority_queue<pi> () ; 
		for(int b=0;b<B;b++){
			mins = mid; 
			while(i < T && BySi[i].s<Y[b]){
				if( !done[BySi[i].ind] && mins){
					q.push({BySi[i].w,BySi[i].ind}); 
				}i++; 
			}
			while(mins&&!q.empty()){
				p = q.top(); 
				q.pop();
				done[p.se]=1; 
				mins--;  
				DONE++; 
			}
		}
		while(!q.empty())q.pop();  
		bool doneAll =(DONE==T); 
		// cout << mid << " " << DONE << endl; 
		// for( i = 0 ; i < T ; i++ )cout << done[i];
		if( doneAll ){
			ans = mid ; 
			r = mid-1; 
		}else {
			l = mid+1; 
		}
	}
	return ans ;
}

// int main(){
// 	int A , B , T ; 
// 	cin >> A >> B >> T ; 

// 	int X[A] , Y[B] , W[T] , S[T] ; 

// 	for(int i = 0 ; i < A ; i++ )cin >> X[i]; 
// 	for(int i = 0 ; i < B ; i++ )cin >> Y[i]; 
// 	for(int i = 0 ; i < T ; i++ ){
// 		cin >> W[i] >> S[i] ;
// 	}
// 	cout << putaway(A,B,T,X,Y,W,S); 
// }

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