Submission #140287

#	Time	Username	Problem	Language	Result	Execution time	Memory
140287		MvC	Robots (IOI13_robots)	C++11	0 / 100	2 ms	552 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 main()
{
	freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>na>>nb>>n;
	for(i=1;i<=na;i++)cin>>we[i];
	for(i=1;i<=nb;i++)cin>>sm[i];
	for(i=1;i<=n;i++)
	{
		cin>>w[i]>>s[i];
		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;
	}
	cout<<rs<<endl;
    return 0;
}
/*
2 1 3
2 5
2
3 1
5 3
2 2

3 2 10
6 2 9
4 7
4 6
8 5
2 3
7 9
1 8
5 1
3 3
8 7
7 6
10 5
*/
int putaway(int Na,int Nb,int N,int We[],int Sm[],int W[],int S[])
{
	na=Na,nb=Nb,n=N;
	for(i=1;i<=na;i++)w[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")
 
robots.cpp:113:1: warning: "/*" within comment [-Wcomment]
 /*

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