oj.uz

Submission #4283

# Submission time Handle Problem Language Result Execution time Memory
4283 2013-09-11T11:47:21 Z cki86201 Robots (IOI13_robots) C++
90 / 100
 796 ms 65536 KB 
#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;}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 comp0(const robot &a,const robot &b){return a.w!=b.w?a.w<b.w:a.s>b.s;}
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=0;i<A;i++)X[i]--;sort(X,X+A);
	for(i=0;i<B;i++)Y[i]--;sort(Y,Y+B);
	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,comp0);
	int c=1;
	for(i=1;i<=T;i++){
		while(c<=A && inp[i].w>X[c-1])c++;
		inp[i].wn=c;
	}
	sort(inp+1,inp+1+T,comp1);
	for(i=c=1;i<=T;i++){
		while(c<=B && inp[i].s>Y[c-1])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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 28752 KB Output is correct
2 Correct 0 ms 28752 KB Output is correct
3 Correct 0 ms 28752 KB Output is correct
4 Correct 0 ms 28752 KB Output is correct
5 Correct 0 ms 28752 KB Output is correct
6 Correct 0 ms 28752 KB Output is correct
7 Correct 0 ms 28752 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 28752 KB Output is correct
2 Correct 0 ms 28752 KB Output is correct
3 Correct 0 ms 28752 KB Output is correct
4 Correct 732 ms 63692 KB Output is correct
5 Correct 352 ms 28752 KB Output is correct
6 Correct 76 ms 32240 KB Output is correct
7 Correct 788 ms 60524 KB Output is correct
8 Correct 768 ms 58224 KB Output is correct
9 Correct 592 ms 59476 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 28752 KB Output is correct
2 Correct 0 ms 28752 KB Output is correct
3 Correct 0 ms 28752 KB Output is correct
4 Correct 0 ms 28752 KB Output is correct
5 Correct 0 ms 28752 KB Output is correct
6 Correct 0 ms 28752 KB Output is correct
7 Correct 0 ms 28752 KB Output is correct
8 Correct 0 ms 28752 KB Output is correct
9 Correct 0 ms 28752 KB Output is correct
10 Correct 0 ms 28752 KB Output is correct
11 Correct 0 ms 28752 KB Output is correct
12 Correct 0 ms 28752 KB Output is correct
13 Correct 0 ms 28752 KB Output is correct
14 Correct 0 ms 28752 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 28752 KB Output is correct
2 Correct 0 ms 28752 KB Output is correct
3 Correct 0 ms 28752 KB Output is correct
4 Correct 0 ms 28752 KB Output is correct
5 Correct 0 ms 28752 KB Output is correct
6 Correct 0 ms 28752 KB Output is correct
7 Correct 0 ms 28752 KB Output is correct
8 Correct 0 ms 28752 KB Output is correct
9 Correct 0 ms 28752 KB Output is correct
10 Correct 0 ms 28752 KB Output is correct
11 Correct 0 ms 28752 KB Output is correct
12 Correct 0 ms 28752 KB Output is correct
13 Correct 0 ms 28752 KB Output is correct
14 Correct 0 ms 28752 KB Output is correct
15 Correct 0 ms 28752 KB Output is correct
16 Correct 8 ms 29280 KB Output is correct
17 Correct 12 ms 29280 KB Output is correct
18 Correct 12 ms 29716 KB Output is correct

Subtask #5
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 28752 KB Output is correct
2 Correct 0 ms 28752 KB Output is correct
3 Correct 0 ms 28752 KB Output is correct
4 Correct 0 ms 28752 KB Output is correct
5 Correct 0 ms 28752 KB Output is correct
6 Correct 0 ms 28752 KB Output is correct
7 Correct 0 ms 28752 KB Output is correct
8 Correct 0 ms 28752 KB Output is correct
9 Correct 0 ms 28752 KB Output is correct
10 Correct 724 ms 63692 KB Output is correct
11 Correct 348 ms 28752 KB Output is correct
12 Correct 72 ms 32240 KB Output is correct
13 Correct 788 ms 60524 KB Output is correct
14 Correct 796 ms 58224 KB Output is correct
15 Correct 0 ms 28752 KB Output is correct
16 Correct 0 ms 28752 KB Output is correct
17 Correct 0 ms 28752 KB Output is correct
18 Correct 0 ms 28752 KB Output is correct
19 Correct 0 ms 28752 KB Output is correct
20 Correct 0 ms 28752 KB Output is correct
21 Correct 12 ms 29280 KB Output is correct
22 Correct 540 ms 59476 KB Output is correct
23 Correct 592 ms 59476 KB Output is correct
24 Memory limit exceeded 492 ms 65536 KB Memory limit exceeded
25 Halted 0 ms 0 KB -