QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#126405#1166. Designing a PCByoungsystemWA 62ms156924kbC++204.1kb2023-07-18 14:44:232023-07-18 14:44:26

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-18 14:44:26]
  • Judged
  • Verdict: WA
  • Time: 62ms
  • Memory: 156924kb
  • [2023-07-18 14:44:23]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int n=0,f=1,ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		n=n*10+ch-'0';
		ch=getchar();
	}
	return n*f;
}
struct bbian
{
	int v,nex;
}a[50000004];
int head[10000004],tmp;
void addb(int x,int y)
{
	//printf("%d %d\n",x,y);
	a[++tmp].v=y;
	a[tmp].nex=head[x];
	head[x]=tmp;
}
int dfn[10000004],low[10000004],cnt;
bool vis[10000004];
int sta[10000004],ttop;
int cid;
int col[10000004];
void tarjan(int x)
{
	dfn[x]=low[x]=++cnt;
	vis[x]=true;
	sta[++ttop]=x;
	for(int i=head[x];i;i=a[i].nex)
	{
		if(dfn[a[i].v]==0)
		{
			tarjan(a[i].v);
			low[x]=min(low[x],low[a[i].v]);
		}
		else if(vis[a[i].v]==true)low[x]=min(low[x],dfn[a[i].v]);
	}
	if(low[x]==dfn[x])
	{
		//printf("!!!\n");
		++cid;
		while(ttop>=1)
		{
			col[sta[ttop]]=cid;
			vis[sta[ttop]]=false;
			if(sta[ttop]==x)
			{
				ttop--;
				break;
			}
			ttop--;
		}
	}
}
int zs;
//0:xia 1:shang
int c[400005];
int dy[400005];
int pre[400005];
vector<int>v[400005];
bool xx[400005];
int pos[400005],qz[400005];
int gd[400005];
bool bi(int x,int y)
{
	return qz[x]<qz[y];
}
int posd[400005];
bool bid(int x,int y)
{
	return dy[x]<dy[y];
}
int ch[5000004][2],ttt;
int rt;
int insert(int k,int l,int r,int x,int y)
{
	if(l==r)return y;
	int o=++ttt;
	ch[o][0]=ch[k][0];
	ch[o][1]=ch[k][1];
	int mid=((l+r)>>1);
	if(x<=mid)ch[o][0]=insert(ch[k][0],l,mid,x,y);
	else ch[o][1]=insert(ch[k][1],mid+1,r,x,y);
	if(ch[o][0]!=0)
	{
		addb(o,ch[o][0]);
		addb(ch[o][0]+zs,o+zs);
	}
	if(ch[o][1]!=0)
	{
		addb(o,ch[o][1]);
		addb(ch[o][1]+zs,o+zs);
	}
	return o;
}
void findlink(int k,int l,int r,int ql,int qr,int x,int fx)
{
	if(l>qr||r<ql||k==0)return;
	if(l>=ql&&r<=qr)
	{
		addb(x,k);
		addb(k+zs,fx);
		return;
	}
	int mid=((l+r)>>1);
	findlink(ch[k][0],l,mid,ql,qr,x,fx);
	findlink(ch[k][1],mid+1,r,ql,qr,x,fx);
}
int main()
{
	zs=5000000;
	int n;
	n=read();
	for(int i=1;i<=2*n;i++)
	{
		c[i]=read();
		v[c[i]].push_back(i);
		if(pre[c[i]]!=0)
		{
			dy[i]=pre[c[i]];
			dy[pre[c[i]]]=i;
			pre[c[i]]=0;
		}
		else pre[c[i]]=i;
	}
	ttt=4*n;
	for(int i=1;i<=2*n;i++)
	{
		addb(i,i+2*n+zs);
		addb(i+2*n,i+zs);
	}
	for(int i=1;i<=2*n;i++)posd[i]=i;
	sort(posd+1,posd+2*n+1,bid);
	//for(int i=1;i<=2*n;i++)printf("%d %d\n",posd[i],dy[posd[i]]);
	int sth=0;
	for(int i=1;i<=2*n;i++)
	{
		sth=max(sth,dy[i]);
		if(i<dy[i]&&sth>dy[i])
		{
			printf("%d %d\n",i,dy[i]);
			addb(i,dy[i]);
			addb(dy[i],i);
			addb(i+zs,dy[i]+zs);
			addb(dy[i]+zs,i+zs);
		}
	}
	rt=0;
	int now=0;
	for(int i=1;i<=2*n;i++)
	{
		while(now<2*n&&dy[posd[now+1]]<=i)
		{
			now++;
			if(dy[posd[now]]<posd[now])
			{
				rt=insert(rt,1,2*n,posd[now],posd[now]);
				//printf("%d\n",rt);
			}
		}
		if(i<dy[i])
		{
			//printf("orz\n");
			findlink(rt,1,2*n,i,dy[i]-1,i+zs,i);
		}
	}
	rt=0;
	now=2*n+1;
	for(int i=2*n;i>=1;i--)
	{
		while(now>1&&dy[posd[now-1]]>=i)
		{
			now--;
			if(dy[posd[now]]>posd[now])
			{
				rt=insert(rt,1,2*n,posd[now],posd[now]+2*n);
			}
		}
		if(i>dy[i])
		{
			findlink(rt,1,2*n,dy[i]+1,i,i,i+zs);
		}
	}
	for(int i=1;i<=2*zs;i++)if(dfn[i]==0)tarjan(i);
	for(int i=1;i<=zs;i++)
	{
		if(col[i]==col[i+zs])
		{
			printf("NO\n");
			return 0;
		}
	}
	printf("YES\n");
	for(int i=1;i<=2*n;i++)
	{
		if(col[i]<col[i+zs])
		{
			xx[i]=true;
		}
	}
	for(int i=1;i<=n;i++)
	{
		int l=v[i][0],r=v[i][1];
		if(xx[l]==xx[r])qz[i]=r-l;
		else qz[i]=r-1+l-1;
		pos[i]=i;
	}
	sort(pos+1,pos+n+1,bi);
	for(int i=1;i<=n;i++)gd[pos[i]]=i;
	for(int i=1;i<=n;i++)
	{
		int l=v[i][0],r=v[i][1],h=gd[i];
		if(xx[l]==true&&xx[r]==true)
		{
			printf("3 D %d R %d U %d\n",h,r-l,h);
		}
		else if(xx[l]==false&&xx[r]==false)
		{
			printf("3 U %d R %d D %d\n",h,r-l,h);
		}
		else if(xx[l]==false&&xx[r]==true)
		{
			printf("5 U %d L %d D %d R %d U %d\n",h,l+h,2*h,r+h,h);
		}
		else if(xx[l]==true&&xx[r]==false)
		{
			printf("5 D %d L %d U %d R %d D %d\n",h,l+h,2*h,r+h,h);
		}
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 53ms
memory: 156924kb

input:

4
1 2 3 4 1 2 3 4

output:

YES
5 D 1 L 2 U 2 R 6 D 1
5 D 3 L 5 U 6 R 9 D 3
5 D 4 L 7 U 8 R 11 D 4
3 D 2 R 4 U 2

result:

ok ok

Test #2:

score: -100
Wrong Answer
time: 62ms
memory: 148952kb

input:

4
1 2 3 4 1 3 2 4

output:

3 6
NO

result:

wrong answer Token "3" doesn't correspond to pattern "YES|NO"