Submission #97070

#	Time	Username	Problem	Language	Result	Execution time	Memory
97070		MvC	Robots (IOI13_robots)	C++11	0 / 100	7 ms	768 KiB

robots

#pragma GCC optimize("O3")
#include "robots.h"
#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e6+50;
const int mod=1e9+7;
using namespace std;
int n,m,t,x[nmax],y[nmax],s[nmax],w[nmax];
multiset<pair<int,int> >sw,ss,st,nw;
multiset<pair<int,int> >::iterator it;
pair<int,int>p;
int ok(int tm)
{
	int i;
	for(i=1;i<=t;i++)
	{
		sw.in(make_pair(w[i],s[i]));
		ss.in(make_pair(s[i],w[i]));
	}
	st.clear(),nw.clear();
	it=sw.begin();
	for(i=1;i<=n;i++)
	{
		for(;it!=sw.end();it++)
		{
			p=(*it);
			if(p.fr>=x[i])break;
			st.in(make_pair(p.sc,p.fr));
		}
		int ct=tm;
		while(!st.empty() && ct--)
		{
			p=(*st.rbegin());
			st.er(st.fd(p));
			nw.in(make_pair(p.sc,p.fr));
			if(ss.fd(p)!=ss.end())ss.er(ss.fd(p));
		}
	}
	st.clear();
	it=ss.begin();
	for(i=1;i<=m;i++)
	{
		for(;it!=ss.end();it++)
		{
			p=(*it);
			if(p.fr>=y[i])break;
			st.in(make_pair(p.sc,p.fr));
		}
		int ct=tm;
		while(!st.empty() && ct--)
		{
			p=(*st.rbegin());
			st.er(st.fd(p));
			if(sw.fd(p)!=sw.end())sw.er(sw.fd(p));
		}
	}
	for(it=nw.begin();it!=nw.end();it++)sw.er(sw.fd(*it));
	return (sw.empty());
}
int putaway(int N,int M,int T,int X[],int Y[],int W[],int S[])
{
	n=N,m=M,t=T;
	int i;
	for(i=1;i<=n;i++)x[i]=X[i-1];
	for(i=1;i<=m;i++)y[i]=Y[i-1];
	for(i=1;i<=t;i++)
	{
		w[i]=W[i-1];
		s[i]=S[i-1];
	}
	int l=1,r=t,mid;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(ok(mid))r=mid-1;
		else l=mid+1;
	}
	if(ok(r+1))return r+1;
	return -1;
}
/*int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	
    return 0;
}*/

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