比赛 |
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;
}