제출 #668238

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
668238		Trumling	로봇 (IOI13_robots)	C++14	28 / 100	159 ms	4576 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[]) 
{
if(a==0 || b==0)
{
	if(a==0)
	{
		swap(a,b);
		swap(y,x);
		swap(W,Se);
	}
	sort(x,x+a);
sort(W,W+t);
 
if(x[a-1]<=W[t-1])
return -1;
 
 
int idx=0;
int arr[a];
for(int i=0;i<a;i++)
{
	while(idx<t && W[idx]<x[i])
	{
		idx++;
	}
	arr[i]=idx;
}
int ans=999999999;
int l=1,r=t+1;
 
while(l<r)
{
	int left=t;
	int minus=0;
	int time=(l+r)/2;
	for(int i=0;i<a;i++)
	{
		left-=min(time,(arr[i]-minus));
		minus+=min(time,(arr[i]-minus));
	}
	if(left==0)
	{
		ans=min(ans,time);
		r=time;
	}
	else
	l=time+1;
}
return ans;
}

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;
}

ll pre=0;
for(int i=0;i<a;i++)
{
	if(pre==arr[i])
	continue;
sort(w+pre,w+arr[i],check);
pre=arr[i];
}


bool taken[t]={ };
ll ans=999999999;
ll l=1,r=t+1;

while(l<r)
{
	ll left=t;
	ll minus=0;
	ll time=(l+r)/2;
	for(int i=0;i<a;i++)
	{
		left-=min(time,(arr[i]-minus));
		for(int j=arr[i]-1;j>=arr[i]-min(time,(arr[i]-minus));j--)
			taken[w[j].S]=true;
		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;
	}
	for(int i=0;i<t;i++)
	taken[i]=0;
}
return ans;

}

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