QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#19647#1166. Designing a PCBwlzhouzhuanWA 3ms3836kbC++173.8kb2022-02-07 15:01:192022-05-06 06:34:30

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-06 06:34:30]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3836kb
  • [2022-02-07 15:01:19]
  • 提交

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

Details

Tip: Click on the bar to expand more detailed information

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"