Submission #202321

#	Time	Username	Problem	Language	Result	Execution time	Memory
202321		mohammad	Robots (IOI13_robots)	C++14	100 / 100	2659 ms	42720 KiB

robots

/*
░░░░██████████████████
░░▄███████▀▀▀▀▀▀███████▄
░▐████▀▒mohammad▒▀██████▄
░███▀▒▒▒▒alaa▒▒▒▒▒▒▀█████
░▐██▒▒▒alwrawrah▒▒▒▒▒████▌
░▐█▌▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒████▌
░░█▒▄▀▀▀▀▀▄▒▒▄▀▀▀▀▀▄▒▐███▌
░░░▐░░░▄▄░░▌▐░░░▄▄░░▌▐███▌
░▄▀▌░░░▀▀░░▌▐░░░▀▀░░▌▒▀▒█▌
░▌▒▀▄░░░░▄▀▒▒▀▄░░░▄▀▒▒▄▀▒▌
░▀▄▐▒▀▀▀▀▒▒▒▒▒▒▀▀▀▒▒▒▒▒▒█
░░░▀▌▒▄██▄▄▄▄████▄▒▒▒▒█▀
░░░░▄██████████████▒▒▐▌
░░░▀███▀▀████▀█████▀▒▌
░░░░░▌▒▒▒▄▒▒▒▄▒▒▒▒▒▒▐
░░░░░▌▒▒▒▒▀▀▀▒▒▒▒▒▒▒▐
*/
 
#include<bits/stdc++.h>
#include "robots.h"
using namespace std;
 
typedef long long ll ;
const ll oo = 1e13 ;
const double PI = acos(-1) ;
const ll M = 1e9 + 7  ;

pair<int , int > w[1000010] , s[1000010] , mp[1000010] ;
int use[1000010], n , m , t;

//=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

bool cmp(const pair<int , int> i, const pair<int,int> j){
	return (i.first != j.first ? i.first < j.first : mp[i.second].second > mp[j.second].second);
}
bool cmp1(const pair<int , int> i, const pair<int,int> j){
	return (i.first != j.first ? i.first < j.first : mp[i.second].first > mp[j.second].first);
}
bool cn(int md , int X[] , int Y[]){
	priority_queue<pair<int,int>> s1;
	int idx = 0;
	int res = 0;
	for(int i = 0 ; i < n ; ++i){
		while(idx != t && w[idx].first < X[i]){
			int id = w[idx].second;
			s1.push({mp[id].second , id});
			idx++;
		}
		int q = md ;
		while(q-- && s1.size()){
			int x = s1.top().second ;
			s1.pop();
			use[x] = 1;
			res++;
		}
	}
	priority_queue<pair<int,int>> qq;
	idx = 0 ;
	for(int i = 0 ; i < m ; ++i){
		while(idx != t && (s[idx].first < Y[i] || use[s[idx].second])){
			int id = s[idx].second;
			if(!use[id])
				qq.push({mp[id].first , id});
			idx++;
		}
		int q = md ;
		while(q-- && qq.size()){
			res++;
			int x = qq.top().second ;
			qq.pop();
			use[x] = 1;
		}
	}
	return (res == t);
}
//=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){
	n = A ;
	m = B ;
	t = T;
	sort(X , X + A) ;
	sort(Y , Y + B) ;
	for(int i = 0 ; i < T ; ++i){
		w[i] = {W[i] , i};
		s[i] = {S[i] , i};
		mp[i] = {W[i] , S[i]};
	}
	sort(w , w + T , cmp);
	sort(s , s + T , cmp1);
	int lo = 0 , hi = T + 1 , ans = -1;
	while(lo <= hi){
		int md = (lo + hi) / 2 ;
		memset(use , 0 , sizeof use);
		if(cn(md , X , Y)){
			hi = md - 1;
			ans = md ;
		}else{
			lo = md + 1;
		}
	}
	return ans;
}

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