oj.uz

Submission #4280

# Submission time Handle Problem Language Result Execution time Memory
4280 2013-09-11T11:33:37 Z cki86201 Robots (IOI13_robots) C++
90 / 100
 772 ms 63696 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;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.0 / 14.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 28756 KB Output is correct
2 Correct 0 ms 28756 KB Output is correct
3 Correct 0 ms 28756 KB Output is correct
4 Correct 684 ms 63696 KB Output is correct
5 Correct 332 ms 28756 KB Output is correct
6 Correct 64 ms 32244 KB Output is correct
7 Correct 768 ms 60528 KB Output is correct
8 Correct 760 ms 58228 KB Output is correct
9 Correct 560 ms 59480 KB Output is correct

Subtask #3
25.0 / 25.0

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

Subtask #4
37.0 / 37.0

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

Subtask #5
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 28756 KB Output is correct
2 Correct 0 ms 28756 KB Output is correct
3 Correct 0 ms 28756 KB Output is correct
4 Correct 0 ms 28756 KB Output is correct
5 Correct 0 ms 28756 KB Output is correct
6 Correct 0 ms 28756 KB Output is correct
7 Correct 0 ms 28756 KB Output is correct
8 Correct 0 ms 28756 KB Output is correct
9 Correct 0 ms 28756 KB Output is correct
10 Correct 688 ms 63696 KB Output is correct
11 Correct 324 ms 28756 KB Output is correct
12 Correct 72 ms 32244 KB Output is correct
13 Correct 760 ms 60528 KB Output is correct
14 Correct 772 ms 58228 KB Output is correct
15 Correct 0 ms 28756 KB Output is correct
16 Correct 0 ms 28756 KB Output is correct
17 Correct 0 ms 28756 KB Output is correct
18 Correct 0 ms 28756 KB Output is correct
19 Correct 0 ms 28756 KB Output is correct
20 Correct 0 ms 28756 KB Output is correct
21 Correct 12 ms 29284 KB Output is correct
22 Incorrect 336 ms 28756 KB Output isn't correct
23 Halted 0 ms 0 KB -