oj.uz

Submission #14861

# Submission time Handle Problem Language Result Execution time Memory
14861 2015-07-01T15:07:06 Z pichulia 올림픽 피자 (tutorial5) C++
70 / 100
 1000 ms 5180 KB 
#include "pizza.h"

#define I 131072
static int order_num;
static int a[8];
struct A{
    int i,d;
	A(){i=0;d=-1;}
};
static A b[2*I];
static A d[2*I];
void Init() {
 
  order_num = 0;
  int i, j;
  for(i=0; i<8; i++)
      a[i] = 0;
  for(i=0;i<2*I;i++)
  {
	  b[i].d = 0;
	  b[i].i = 0;
	  d[i].d = 0;
	  d[i].i = 0;
  }
}
void Order(int N, int *A) {
 
    int i, j, k=0;
	j=0;
	for(i=0;i<N;i++)
		k += (1<<A[i]);
	for(i=0;i<8;i++)
		if(a[i])
			j += (1<<i);
	if((k&j) == k)
	{
		for(i=0;i<N;i++)
			a[A[i]]--;
		Bake(order_num);
	}
	else
	{
		struct A c;
		c.d = k;
		c.i = order_num;
		i =order_num + I; 
		b[i] = c;
		d[i] = c;
		i/=2;
		while(i>0)
		{
			b[i].i = b[i*2].i + b[i*2+1].i;
			b[i].d = b[i*2].d | b[i*2+1].d;
			d[i].i = d[i*2].i + d[i*2+1].i;
			d[i].d = d[i*2].d & d[i*2+1].d;
			i/=2;
		}
	}
    order_num++;
}
 A find(int dep, int j, int k)
 {
	 if((d[dep].d & j) == d[dep].d && (b[dep].d | k) == b[dep].d)
	 {
		if(dep >= I) return b[dep];
		 A p = find(dep*2,j,k);
		 if(p.d >= 0) return p;
		 return find(dep*2+1,j,k);
	 }
	 else
		 return A();
 }
void Delivery(int x) {
 
    a[x]++;
	if(a[x] == 1)
	{
		int i, j, k;
		j=0;
		for(i=0;i<8;i++)
			if(a[i])
				j+=(1<<i);
		k=1<<x;
		struct A c=find(1,j,k);
		if(c.d >= 0)
		{
			Bake(c.i);
			for(i=0;i<8;i++)
				if((c.d &(1<<i)) == (1<<i))
					a[i]--;
			i =c.i + I; 
			c.i=c.d=0;
			b[i] = c;
			d[i] = c;
			i/=2;
			while(i>0)
			{
				b[i].i = b[i*2].i + b[i*2+1].i;
				b[i].d = b[i*2].d | b[i*2+1].d;
				d[i].i = d[i*2].i + d[i*2+1].i;
				d[i].d = d[i*2].d & d[i*2+1].d;
				i/=2;
			}
		}
	}
}

Subtask #1
25.0 / 25.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5180 KB Output is correct
2 Correct 12 ms 5180 KB Output is correct
3 Correct 21 ms 5180 KB Output is correct
4 Correct 21 ms 5180 KB Output is correct
5 Correct 25 ms 5180 KB Output is correct
6 Correct 25 ms 5180 KB Output is correct
7 Correct 22 ms 5180 KB Output is correct
8 Correct 24 ms 5180 KB Output is correct
9 Correct 21 ms 5180 KB Output is correct
10 Correct 23 ms 5180 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 5180 KB Output is correct
2 Correct 51 ms 5180 KB Output is correct
3 Correct 45 ms 5180 KB Output is correct
4 Correct 52 ms 5180 KB Output is correct
5 Correct 59 ms 5180 KB Output is correct
6 Correct 52 ms 5180 KB Output is correct
7 Correct 36 ms 5180 KB Output is correct
8 Correct 54 ms 5180 KB Output is correct
9 Correct 49 ms 5180 KB Output is correct
10 Correct 43 ms 5180 KB Output is correct

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 5180 KB Program timed out
2 Halted 0 ms 0 KB -