Submission #668635

#	Time	Username	Problem	Language	Result	Execution time	Memory
668635		Dremix10	Robots (IOI13_robots)	C++17	100 / 100	1870 ms	41060 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';
 
int putaway(int a, int b, int t, int x[], int y[], int W[], int Se[]) 
{
pair<ll,ll> w[t],s[t];
for(int i=0;i<t;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=9999999999;
ll l=1,r=t+1;
 
priority_queue<pair<ll,ll>>pq;
 
while(l<r)
{
	ll left=t;
	ll minus=0;
	ll time=(l+r)/2;
	ll pre=0;
	for(int i=0;i<a;i++)
	{
		for(int j=pre;j<arr[i];j++)
			pq.push({Se[w[j].S],w[j].S});
			
	
		pre=arr[i];
		ll c=time;
        int cnt = 0;
        assert(arr[i]-minus == (ll)pq.size());
		while(!pq.empty() && c--)
		{
			taken[pq.top().S]=true;
			pq.pop();
            cnt++;
            //left--;
		}
       // assert(0);
        //assert(arr)
        //assert(cnt == min(time,(arr[i]-minus)));
		left-=min(time,(arr[i]-minus));
		minus+=min(time,(arr[i]-minus));
	}
	
	
		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;
	


	for(int i=0;i<t;i++)
	taken[i]=0;
	while(!pq.empty()){
		pq.pop();
	}
}
return ans;
 
}

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