Submission #1072241

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072241		LCJLY	Robots (IOI13_robots)	C++14	100 / 100	1070 ms	36152 KiB

robots

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

#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef array<int,4>pi2;

int putaway(int a, int b, int t, int X[], int Y[], int w[], int s[]){
	int arr[a];
	for(int x=0;x<a;x++) arr[x]=X[x];
	int arr2[b];
	for(int x=0;x<b;x++) arr2[x]=Y[x];
	
	sort(arr,arr+a);
	sort(arr2,arr2+b);
	vector<pii>storage[a+5];
	vector<int>storage2[b+5];
	for(int x=0;x<t;x++){
		int index=upper_bound(arr,arr+a,w[x])-arr;
		int index2=upper_bound(arr2,arr2+b,s[x])-arr2;
		if(index==a&&index2==b) return -1;
		storage[index].push_back({index2,x});
		storage2[index2].push_back(x);
	}
	
	int l=1;
	int r=1e6;
	int mid;
	int best=-1;
	while(l<=r){
		mid=(l+r)/2;
		bool done[t+5];
		memset(done,0,sizeof(done));
		priority_queue<pii>pq;
		for(int x=0;x<a;x++){
			for(auto it:storage[x]){
				pq.push(it);
			}
			for(int y=0;y<mid;y++){
				if(pq.empty()) break;
				pii cur=pq.top();
				pq.pop();
				done[cur.second]=true;
			}
		}
		
		while(!pq.empty()) pq.pop();
		for(int x=0;x<b;x++){
			for(auto it:storage2[x]){
				if(done[it]) continue;
				pq.push({1,it});
			}
			for(int y=0;y<mid;y++){
				if(pq.empty()) break;
				pii cur=pq.top();
				pq.pop();
				done[cur.second]=true;
			}
		}
		bool amos=true;
		for(int y=0;y<t;y++) amos&=done[y];
		if(amos){
			best=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	return best;
}

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