Submission #4280

#	Time	Username	Problem	Language	Result	Execution time	Memory
4280		cki86201	Robots (IOI13_robots)	C++98	90 / 100	772 ms	63696 KiB

robots

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

const int INF=0x7fffffff;
struct robot{int w,s,wn,sn,n;bool operator<(const robot &l)const{return w!=l.w?w<l.w:s>l.s;}}inp[1000010];
int a,b,t;
int np[50010],nq[50010];
bool check[1000010];

vector <robot> Ww[50010],Ss[50010];
vector <int> WL,SL;
bool comp1(const robot &a,const robot &b){return a.s!=b.s?a.s<b.s:a.w>b.w;}
bool comp2(const robot &a,const robot &b){return a.wn!=b.wn?a.wn<b.wn:a.sn>b.sn;}
bool comp3(const robot &a,const robot &b){return a.sn!=b.sn?a.sn<b.sn:a.wn>b.wn;}

bool solve(int x)
{
	WL.clear();SL.clear();
	int i,C=0;
	for(i=1;i<=a;i++)np[i]=0;
	for(i=1;i<=b;i++)nq[i]=0;
	for(i=1;i<=a;i++){
		int u,j=i;
		for(u=1;u<=x;){
			if(np[j]==Ww[j].size()){
				if(WL.empty())break;
				else{if(j!=i)WL.pop_back();if(WL.empty())break;j=WL.back();}
			}
			check[Ww[j][np[j]].n]=1;
			np[j]++;
			C++;
			if(C==t)return true;
			if(np[j]==Ww[j].size()){
				if(WL.empty())break;
				else{if(j!=i)WL.pop_back();if(WL.empty())break;j=WL.back();}
			}
			if(u==x&&j==i&&np[j]!=Ww[j].size())WL.push_back(i);
			u++;
		}
	}
	for(i=1;i<=b;i++){
		int u,j=i;
		for(u=1;u<=x;){
			if(nq[j]==Ss[j].size()){
				if(SL.empty())break;
				else{if(j!=i)SL.pop_back();if(SL.empty())break;j=SL.back();}
			}
			if(check[Ss[j][nq[j]].n]){nq[j]++;continue;}
			check[Ss[j][nq[j]].n]=1;
			nq[j]++;
			C++;
			if(C==t)return true;
			if(nq[j]==Ss[j].size()){
				if(SL.empty())break;
				else{if(j!=i)SL.pop_back();if(SL.empty())break;j=SL.back();}
			}
			if(u==x&&j==i&&nq[j]!=Ss[j].size())SL.push_back(i);
			u++;
		}
	}
	return false;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	int i;
	a=A;b=B;t=T;
	for(i=A;i;i--)X[i]=X[i-1]-1;sort(X+1,X+1+A);X[A+1]=INF;
	for(i=B;i;i--)Y[i]=Y[i-1]-1;sort(Y+1,Y+1+B);Y[B+1]=INF;
	for(i=1;i<=T;i++){inp[i].w=W[i-1];inp[i].s=S[i-1];inp[i].n=i;}
	sort(inp+1,inp+1+T);
	int c=1;
	for(i=1;i<=T;i++){
		while(inp[i].w>X[c])c++;
		inp[i].wn=c;
	}
	sort(inp+1,inp+1+T,comp1);
	for(i=c=1;i<=T;i++){
		while(inp[i].s>Y[c])c++;
		inp[i].sn=c;
		if(c>B&&inp[i].wn>A){return -1;}
	}
	sort(inp+1,inp+1+T,comp2);
	for(i=1;i<=T;i++)Ww[inp[i].wn].push_back(inp[i]);
	sort(inp+1,inp+1+T,comp3);
	for(i=1;i<=T;i++)Ss[inp[i].sn].push_back(inp[i]);
	int st=T/(A+B),en=T,mi,ans;
	while(st<=en){
		mi=(st+en)>>1;
		memset(check,0,sizeof(check));
		if(solve(mi)){
			ans=mi;
			en=mi-1;
		}
		else st=mi+1;
	}
	return ans;
}

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