QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#126405 | #1166. Designing a PCB | youngsystem | WA | 62ms | 156924kb | C++20 | 4.1kb | 2023-07-18 14:44:23 | 2023-07-18 14:44:26 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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"