Submission #140308

#	Time	Username	Problem	Language	Result	Execution time	Memory
140308		MvC	Robots (IOI13_robots)	C++11	90 / 100	3053 ms	33580 KiB

robots

#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
#include "robots.h"
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#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 mmax=5e4+50;
const int mod=1e9+7;
using namespace std;
int n,m,i,j,na,nb,we[mmax],sm[mmax],s[nmax],w[nmax],nr[mmax],l,r,mid,b[nmax],rs;
set<int>st;
set<int>::iterator it;
pair<int,int>a[nmax];
pair<pair<int,int>,int>v[nmax];
bitset<nmax>vz;
int ok(int x)
{
	int i,y,z,j,tot=0,u;
	st.clear();
	for(i=1;i<=na;i++)
	{
		st.in(i);
		nr[i]=0;
	}
	vz.reset();
	for(i=1;i<=m;i++)
	{
		it=st.lower_bound(v[i].sc);
		if(it==st.end())continue;
		y=(*it);
		nr[y]++;
		if(nr[y]==x)st.er(it);
		vz[v[i].fr.sc]=1;
		tot++;
	}
	u=0;
	for(i=1;i<=n;i++)
	{
		if(vz[i])continue;
		b[++u]=s[i];
	}
	if(u)
	{
		sort(b+1,b+u+1);
		j=1;
		for(i=1;i<=nb;i++)
		{
			z=0;
			for(;j<=u;j++)
			{
				if(b[j]>=sm[i])break;
				if(z==x)break;
				z++;
				tot++;
			}
		}
	}
	return (tot==n);
}
int putaway(int Na,int Nb,int N,int We[],int Sm[],int W[],int S[])
{
	na=Na,nb=Nb,n=N;
	if(na>nb)
	{
		swap(na,nb);
		swap(We,Sm);
		swap(W,S);
	}
	for(i=1;i<=na;i++)we[i]=We[i-1];
	for(i=1;i<=nb;i++)sm[i]=Sm[i-1];
	for(i=1;i<=n;i++)
	{
		w[i]=W[i-1],s[i]=S[i-1];
		a[i]=mkp(w[i],i);
	}
	sort(a+1,a+n+1);
	sort(we+1,we+na+1);
	sort(sm+1,sm+nb+1);
	m=1;
	for(i=1;i<=na;i++)
	{
		for(;m<=n;m++)
		{
			if(we[i]<=a[m].fr)break;
			v[m]=mkp(mkp(s[a[m].sc],a[m].sc),i);
			//cout<<v[m].fr.fr<<" "<<v[m].fr.sc<<" "<<v[m].sc<<endl;
		}
	}
	m--;
	sort(v+1,v+m+1);
	reverse(v+1,v+m+1);
	l=1,r=n,rs=-1;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(ok(mid))r=mid-1,rs=mid;
		else l=mid+1;
	}
	return rs;
}

Compilation message (stderr)

robots.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
robots.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")

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