QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#19647 | #1166. Designing a PCB | wlzhouzhuan | WA | 3ms | 3836kb | C++17 | 3.8kb | 2022-02-07 15:01:19 | 2022-05-06 06:34:30 |
Judging History
answer
// Author: wlzhouzhuan
#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,l,r) for(int i=(l);i>=(r);i--)
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define mset(s,t) memset(s,t,sizeof(s))
#define mcpy(s,t) memcpy(s,t,sizeof(t))
#define SZ(x) ((int)x.size())
#define pb push_back
#define eb emplace_back
#define fir first
#define sec second
template<class T1,class T2>bool ckmax(T1 &a,T2 b){if(a<b)return a=b,1;else return 0;}
template<class T1,class T2>bool ckmin(T1 &a,T2 b){if(a>b)return a=b,1;else return 0;}
inline int read(){
int x=0,f=0;char ch=getchar();
while(!isdigit(ch))f|=ch=='-',ch=getchar();
while(isdigit(ch))x=10*x+ch-'0',ch=getchar();
return f?-x:x;
}
template<typename T>void print(T x){
if(x<0)putchar('-'),x=-x;
if(x>=10)print(x/10);
putchar(x%10+'0');
}
template<typename T>void print(T x,char ch){
print(x),putchar(ch);
}
const int N=5005;
int p[N],n,L[N],R[N];
int op[N],H[N],dis[N];
#define yes(u) (2*u-1)
#define no(u) (2*u)
vector<int>adj[N];
inline void same(int x,int y){
adj[yes(x)].pb(yes(y));
adj[yes(y)].pb(yes(x));
adj[no(x)].pb(no(y));
adj[no(y)].pb(no(x));
}
inline void diff(int x,int y){
printf("???\n");
adj[yes(x)].pb(no(y));
adj[yes(y)].pb(no(x));
adj[no(x)].pb(yes(y));
adj[no(y)].pb(yes(x));
}
int dfn[N],low[N],be[N],comp,dtot;
bool instk[N];
stack<int>stk;
void tarjan(int u){
dfn[u]=low[u]=++dtot,instk[u]=1,stk.push(u);
for(auto v:adj[u]){
if(!dfn[v]){
tarjan(v);
ckmin(low[u],low[v]);
}else if(instk[v]){
ckmin(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
int y;comp++;
while(y=stk.top()){
be[y]=comp,instk[y]=0,stk.pop();
if(y==u)break;
}
}
}
int main(){
n=read();
rep(i,1,2*n)p[i]=read();
rep(i,1,n){
rep(j,1,2*n){
if(p[j]==i){
if(!L[i])L[i]=j;
else R[i]=j;
}
}
}
rep(j,1,n){
bool flag=0;
rep(i,1,n){
if(L[i]<L[j]&&R[j]<R[i])
flag=1;
}
if(flag)same(L[j],R[j]);
}
rep(i,1,n){
rep(j,1,n){
if(L[i]<L[j]&&L[j]<R[i]&&R[i]<R[j])
diff(L[j],R[i]);
}
}
rep(i,1,4*n)if(!dfn[i])tarjan(i);
rep(i,1,2*n){
if(be[yes(i)]==be[no(i)])return puts("NO"),0;
op[i]=be[yes(i)]<be[no(i)];
}
puts("YES");
int now=5000;
rep(i,1,2*n)if(op[i]){
int l=L[p[i]],r=R[p[i]];
if(i==l)H[i]=now--;
else if(op[r])H[i]=H[l];
else H[i]=now--;
}
now=5000;
rep(i,1,2*n)if(!op[i]){
int l=L[p[i]],r=R[p[i]];
if(i==l)H[i]=now--;
else if(!op[r])H[i]=H[l];
else H[i]=now--;
}
now=5000;
rep(i,1,2*n){
int l=L[p[i]],r=R[p[i]];
if(op[l]!=op[r]&&i==r)dis[p[i]]=now--;
}
/*
rep(i,1,n){
printf("L[%d]=%d,R[%d]=%d\n",i,L[i],i,R[i]);
}
rep(i,1,2*n){
printf("op[%d]=%d\n",i,op[i]);
}
puts("-----");
*/
rep(i,1,n){
int l=L[i],r=R[i];
if(op[l]==op[r]){
if(op[l]){
printf("3 D %d R %d U %d\n",H[l],r-l,H[r]);
}else{
printf("3 U %d R %d D %d\n",H[l],r-l,H[r]);
}
}else{
if(op[l]){
printf("5 D %d R %d U %d L %d D %d\n",H[l],dis[i]-l,H[l]+H[r],dis[i]-r,H[r]);
}else{
printf("5 U %d R %d D %d L %d U %d\n",H[l],dis[i]-l,H[l]+H[r],dis[i]-r,H[r]);
}
}
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 3836kb
input:
4 1 2 3 4 1 2 3 4
output:
??? ??? ??? ??? ??? ??? YES 5 D 5000 R 4999 U 10000 L 4995 D 5000 5 D 4999 R 4997 U 9998 L 4993 D 4999 5 D 4998 R 4995 U 9996 L 4991 D 4998 3 D 4997 R 4 U 4997
result:
wrong answer Token "???" doesn't correspond to pattern "YES|NO"