Submission #14861

#	Time	Username	Problem	Language	Result	Execution time	Memory
14861		pichulia	올림픽 피자 (tutorial5)	C++98	70 / 100	1000 ms	5180 KiB

tutorial5

#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 / 25
• Subtask 2: 25 / 25
• Subtask 3: 20 / 20
• Subtask 4: 0 / 30