Submission #140335

#	Time	Username	Problem	Language	Result	Execution time	Memory
140335		MvC	Robots (IOI13_robots)	C++11	90 / 100	3041 ms	26616 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,st[4*mmax];
pair<int,int>a[nmax],aa[nmax];
pair<pair<int,int>,int>v[nmax];
bool vz[nmax];
void upd(int nod,int l,int r,int p,int v)
{
	if(l==r)
	{
		st[nod]=v;
		return;
	}
	int mid=(l+r)/2;
	if(p<=mid)upd(2*nod,l,mid,p,v);
	else upd(2*nod+1,mid+1,r,p,v);
	st[nod]=st[2*nod]+st[2*nod+1];
}
int qry(int nod,int l,int r,int tl,int tr)
{
	if(tr<l || tl>r)return 0;
	if(tl<=l && r<=tr)return st[nod];
	int mid=(l+r)/2;
	return qry(2*nod,l,mid,tl,tr)+qry(2*nod+1,mid+1,r,tl,tr);
}
int kth(int x,int l,int r,int k)
{
	if(st[x]<k)return -1;
	if(l==r)return l;
	int mid=(l+r)/2;
	if(st[2*x]>=k)return kth(2*x,l,mid,k);
	else return kth(2*x+1,mid+1,r,k-st[2*x]);
}
int ok(int x)
{
	int i,y,z,j,tot=0,u;
	for(i=1;i<=na;i++)
	{
		upd(1,1,na,i,1);
		nr[i]=0;
	}
	for(i=1;i<=m;i++)
	{
		if(!st[1])break;
		if(v[i].sc>1)z=qry(1,1,na,1,v[i].sc-1)+1;
		else z=1;
		y=kth(1,1,na,z);
		if(y==-1)continue;
		nr[y]++;
		if(nr[y]==x)upd(1,1,na,y,0);
		vz[v[i].fr.sc]=1;
		tot++;
	}
	u=0;
	for(i=1;i<=n;i++)
	{
		if(vz[aa[i].sc])
		{
			vz[aa[i].sc]=0;
			continue;
		}
		b[++u]=aa[i].fr;
	}
	if(u)
	{
		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);
		aa[i]=mkp(s[i],i);
	}
	sort(a+1,a+n+1);
	sort(we+1,we+na+1);
	sort(sm+1,sm+nb+1);
	sort(aa+1,aa+n+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