Submission #668639

#	Time	Username	Problem	Language	Result	Execution time	Memory
668639		Trumling	Robots (IOI13_robots)	C++14	100 / 100	1999 ms	34056 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';

pair<ll,ll> w[1000001],s[1000001];
ll SEC[1000001];
bool check(pair<ll,ll>a,pair<ll,ll>b)
{
	return SEC[a.S] < SEC[b.S];
}

int putaway(int a, int b, int t, int x[], int y[], int W[], int Se[]) 
{
for(int i=0;i<t;i++)
{
	SEC[i]=Se[i];
	w[i].F=W[i];
	w[i].S=i;
 
	s[i].F=Se[i];
	s[i].S=i;
}
sort(x,x+a);
sort(y,y+b);
 
sort(w,w+t);
sort(s,s+t);
 
if((x[a-1]<=w[t-1].F && y[b-1]<=Se[w[t-1].S]) || (y[b-1]<=s[t-1].F && x[a-1]<=W[s[t-1].S]) ) 
return -1;
 
 
ll idx=0;
ll arr[a];
for(int i=0;i<a;i++)
{
	while(idx<t && w[idx].F<x[i])
	{
		idx++;
	}
	arr[i]=idx;
}
 
 
bool taken[t]={ };
ll ans=t+3;
ll l=1,r=t+1;
 
priority_queue<pair<ll,ll>>pq;
 
while(l<r)
{
	for(ll i=0;i<t;i++)
	taken[i]=false;

	while(!pq.empty())
	pq.pop();
	ll left=t;
	ll minus=0;
	ll time=(l+r)/2;
	ll pre=0;
	for(int i=0;i<a;i++)
	{
		for(ll j=pre;j<arr[i];j++)
			pq.push({SEC[w[j].S],w[j].S});

		pre=arr[i];	

		left-=min(time,(arr[i]-minus));	
		
		ll count=0;
		while(count!=min((arr[i]-minus),time))
		{
			taken[pq.top().S]=true;
			pq.pop();
			count++;
		}
		minus+=min(time,(arr[i]-minus));
	}
	if(left==0)
	{
		ans=min(ans,time);
		r=time;
	}
	else
	{
		ll idx2=0;
		ll arr2[b];
		ll count=0;
			for(int i=0;i<b;i++)
			{
				while(idx2<t && s[idx2].F<y[i])
				{
					if(taken[s[idx2].S])
					count++;
					idx2++;
				}
				arr2[i]=idx2-count;
			}
		minus=0;
		for(int i=0;i<b;i++)
		{
		left-=min(time,(arr2[i]-minus));
		minus+=min(time,(arr2[i]-minus));
		}
 
		if(left==0)
		{
		ans=min(ans,time);
		r=time;
		}
		else
		l=time+1;
	}
	
}
return ans;
 
}

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