比赛 20120706 评测结果 ATTTTATTTA
题目名称 校草 最终得分 30
用户昵称 ZhouHang 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2012-07-06 11:04:25
显示代码纯文本
#include <cstdio>
#include <cstring>
#include <vector>

#define MaxN 1000100

using namespace std;

struct handsome {
	int a,b,c,d;
}a[MaxN];

struct  node {
	handsome v;
	int num,c[2],p,sz;
	bool d;
} T[MaxN];
int n=0,root=0,tot =0;
int ans;
bool left[MaxN],v[MaxN];
vector <int> q;

int comp(int x,handsome y)
{
	bool tm1 = a[x].a<y.a?1:0;
	bool tm2 = a[x].b<y.b?1:0;
	bool tm3 = a[x].c<y.c?1:0;
	bool tm4 = a[x].d<y.d?1:0;
	if (tm1+tm2+tm3+tm4==4) return 1;
	if (tm1+tm2+tm3+tm4==0) return 0;
	return 2;
}
bool comp2(int x,int y)
{
	bool tm1 = a[x].a<a[y].a?1:0;
	bool tm2 = a[x].b<a[y].b?1:0;
	bool tm3 = a[x].c<a[y].c?1:0;
	bool tm4 = a[x].d<a[y].d?1:0;
	if (tm1+tm2+tm3+tm4>=3) return 1;
	return 0;
}
void copy(handsome &x,handsome y)
{
	x.a = y.a; x.b = y.b;
	x.c = y.c; x.d = y.d;
}
void upd(int x) 
{
	T[x].sz = T[T[x].c[0]].sz + T[T[x].c[1]].sz + 1;
}
//_p的_d子树变为_c
void sc(int _p,int _c,int _d)
{
	T[_p].c[_d] = _c; T[_c].p = _p; T[_c].d = _d;
}
void rot(int x)
{
	int y = T[x].p;
	bool d = T[x].d;
	if (y == root) {root = x; T[root] .p = 0;}
	else sc(T[y].p,x,T[y].d);
	sc(y,T[x].c[!d],d); sc(x,y,!d);
	upd(y);
}
void splay(int x,int r) 
{
	int p,p0;
	while ( (p0=T[x].p) != r) {
		p = T[p0].p;
		if (p==r) rot(x);
		else if (T[x].d == T[p0].d) {rot(p0); rot(x);}
				else {rot(x); rot(x);}		
	}
}
void ins(int x)
{
	if (!root) {
		copy(T[++n].v,a[x]);
		T[n].num = x;
		T[n].c[0] = T[n].c[1] = T[n].p = 0;
		T[n].sz = 1; root = n;
		v[x] = true;
		tot++;
		return;
	}
	int i = root,j;
	while (1) {
		T[i].sz++;
		int cc = comp(x,T[i].v);
		if (cc>1) cc= 1;
		j = T[i].c[cc];
		if (!j) break;
		else i = j;
	}
	int cc = comp(x,T[i].v);
	if (cc>1) return;
	copy(T[++n].v,a[x]); 
	v[x] = true;tot++;
	T[n].num = x; T[n].sz = 1;
	T[n].c[0] = T[n].c[1] = 0;
	sc(i,n,comp(x,T[i].v));
	splay(n,0);
}
void Find_ans(int x)
{
	int now = x;
	while (T[x].c[1]) {
		x = T[x].c[1];
	}
	q.push_back(T[x].num);
}

int main()
{
	freopen("hjjhvf.in","r",stdin);
	freopen("hjjhvf.out","w",stdout);
	
	int tmn;
	scanf("%d",&tmn);
	memset(v,false,sizeof(v));
	tot = 0;
	for (int i=1; i<=tmn; i++) {
		scanf("%d%d%d%d",&a[i].a,&a[i].b,&a[i].c,&a[i].d);
		ins(i);
	}
	//cal
	Find_ans(root);
	
	while (tot!=tmn) {
		n = root = 0;
		for (int i=1; i<=tmn; i++) 
			if (!v[i]) ins(i);
		//cal
		Find_ans(root);
	}
	
	memset(left,false,sizeof(left));
	for (int i=0; i<q.size(); i++)
		left[q[i]] =true;
	for (int  i=0; i<q.size(); i++)
		for (int j=0; j<q.size(); j++)
			if (comp2(q[i],q[j])) left[q[j]] = false;
	
	ans = 0;
	for (int i=1; i<=tmn; i++)
		if (!left[i]) ans++;
			
			
	printf("%d\n",ans);
	for (int i=1; i<=tmn; i++)
		if (!left[i]) printf("%d\n",i);
	
	fclose(stdin); fclose(stdout);
	return 0;
}