Submission #1779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1779		ainta	Robots (IOI13_robots)	C++98	100 / 100	1112 ms	38932 KiB

robots

#include "robots.h"
#include <stdio.h>
#include <algorithm>
using namespace std;

bool v[1000001],vv[150000];
struct A{
	int w,s,x;
	bool operator <(const A &q)const{
		return w<q.w;
	}
}p[1000001];
struct B{
	int w,s,x;
	bool operator <(const B &p)const{
		return s<p.s;
	}
}q[1000001];
int E[1000001],F[1000001],SZ=65536;
long long IT[150001];
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    int i,be=1,ed=T,M,Res;
	sort(X,X+A);
	sort(Y,Y+B);
	for(i=0;i<T;i++)if((A==0||W[i]>=X[A-1])&&(B==0||S[i]>=Y[B-1]))break;
	if(i!=T)return -1;
	for(i=0;i<T;i++){
		p[i].w=W[i],p[i].s=S[i],q[i].w=W[i],q[i].s=S[i];
		p[i].x=q[i].x=i;
	}
	sort(p,p+T);
	sort(q,q+T);
	int c=0;
	for(i=0;i<A;i++){
		while(c<T && X[i]>p[c].w)
		{
			E[p[c++].x]=i;
		}
	}
	while(c<T)E[p[c++].x]=i;
	c=0;
	for(i=0;i<B;i++){
		while(c<T && Y[i]>q[c].s)
			F[q[c++].x]=i;
	}
	while(c<T)F[q[c++].x]=i;
	int t;
	for(i=1;i<150000;i=i*2+1)vv[i]=true;
	while(be<=ed){
		M=(be+ed+1)>>1;
		for(i=0;i<B;i++)IT[SZ+i]=M;
		for(i=SZ-1;i>=1;i--)IT[i]=IT[i*2]+IT[i*2+1];
		for(i=0;i<T;i++)v[i]=false;
		for(i=T-1;i>=0;i--){
			t=F[p[i].x]+SZ;
			while(IT[t]==0LL){
				if(vv[t]){
					break;
				}
				t=(t+1)>>1;
			}
			if(!IT[t])continue;
			while(t<SZ){
				t<<=1;
				if(!IT[t])t++;
			}
			while(t){
				IT[t]--;
				t>>=1;
			}
			v[p[i].x]=true;
		}
		c=0;
		for(i=T-1;i>=0;i--){
			if(!v[p[i].x]){
				c++;
				if((A-E[p[i].x])<=(c-1)/M)break;
			}
		}
		if(i==-1)Res=M,ed=M-1;
		else be=M+1;
	}
	return Res;
}

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