oj.uz

Submission #1779

# Submission time Handle Problem Language Result Execution time Memory
1779 2013-07-15T09:24:27 Z ainta Robots (IOI13_robots) C++
100 / 100
 1112 ms 38932 KB 
#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.0 / 14.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 38932 KB Output is correct
2 Correct 0 ms 38932 KB Output is correct
3 Correct 0 ms 38932 KB Output is correct
4 Correct 900 ms 38932 KB Output is correct
5 Correct 160 ms 38932 KB Output is correct
6 Correct 76 ms 38932 KB Output is correct
7 Correct 912 ms 38932 KB Output is correct
8 Correct 936 ms 38932 KB Output is correct
9 Correct 924 ms 38932 KB Output is correct

Subtask #3
25.0 / 25.0

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

Subtask #4
37.0 / 37.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 38932 KB Output is correct
2 Correct 0 ms 38932 KB Output is correct
3 Correct 0 ms 38932 KB Output is correct
4 Correct 0 ms 38932 KB Output is correct
5 Correct 0 ms 38932 KB Output is correct
6 Correct 0 ms 38932 KB Output is correct
7 Correct 0 ms 38932 KB Output is correct
8 Correct 0 ms 38932 KB Output is correct
9 Correct 0 ms 38932 KB Output is correct
10 Correct 912 ms 38932 KB Output is correct
11 Correct 172 ms 38932 KB Output is correct
12 Correct 72 ms 38932 KB Output is correct
13 Correct 880 ms 38932 KB Output is correct
14 Correct 904 ms 38932 KB Output is correct
15 Correct 0 ms 38932 KB Output is correct
16 Correct 0 ms 38932 KB Output is correct
17 Correct 0 ms 38932 KB Output is correct
18 Correct 0 ms 38932 KB Output is correct
19 Correct 0 ms 38932 KB Output is correct
20 Correct 0 ms 38932 KB Output is correct
21 Correct 8 ms 38932 KB Output is correct
22 Correct 1052 ms 38932 KB Output is correct
23 Correct 928 ms 38932 KB Output is correct
24 Correct 680 ms 38932 KB Output is correct
25 Correct 828 ms 38932 KB Output is correct
26 Correct 448 ms 38932 KB Output is correct
27 Correct 968 ms 38932 KB Output is correct
28 Correct 1000 ms 38932 KB Output is correct
29 Correct 1112 ms 38932 KB Output is correct