QOJ.ac

QOJ

ID	Submission ID	Problem	Hacker	Owner	Result	Submit time	Judge time
#996	#641108	#6817. Permutation Puzzle	czc	czc	Success!	2024-10-14 18:36:13	2024-10-14 18:36:14

Details

Extra Test:

Wrong Answer

time: 0ms

memory: 10308kb

input:

1
3000 5000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2940 0 0 0 0 0 0 0 0 0 0 0 0 371 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

2989 3000 2999 2992 2858 2937 2856 2997 2803 2800 2930 2927 2996 133 2794 2988 2971 2854 2745 2851 2740 2853 2744 2974 2799 6 2730 2725 2701 2924 2696 2986 2980 2692 68 2689 2673 2669 2985 2923 2793 2912 2928 2982 2966 2663 2984 2956 2967 2659 2721 2656 2911 2647 2646 2790 2632 2602 2568 2567 2562 2...

result:

wrong answer The solution does not satisfy p[169] < p[1800]. (test case 1)

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#641108	#6817. Permutation Puzzle	czc	WA	377ms	37756kb	C++23	2.1kb	2024-10-14 18:34:15	2024-10-14 18:37:09

answer

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
vector<int> G[maxn],RG[maxn];
int n,m,ind[maxn];
int ind1[maxn],ind2[maxn],a[maxn],vis[maxn];
int fmn[maxn],fmx[maxn];
inline void solve(){
    set<int> st;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) vis[i]=0,ind1[i]=ind2[i]=ind[i]=0;
    for(int i=1;i<=n;i++) G[i].clear(),RG[i].clear();
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i]) fmn[i]=fmx[i]=a[i];
        else fmn[i]=1,fmx[i]=n; 
        vis[a[i]]=1;
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            st.insert(i);
        }
    }
    for(int i=1,x,y;i<=m;i++){
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        RG[y].push_back(x);
        ind1[y]++;
        ind2[x]++;
        ind[y]++;
    }
    queue<int> q;
    for(int i=1;i<=n;i++) if(!ind1[i]) q.push(i);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(auto y:G[x]){
            ind1[y]--;
            fmn[y]=max(fmn[y],fmn[x]);
            if(!ind1[y]) q.push(y);
        }
    }
    for(int i=1;i<=n;i++) if(!ind2[i]) q.push(i);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(auto y:RG[x]){
            ind2[y]--;
            fmx[y]=min(fmx[y],fmx[x]);
            if(!ind2[y]) q.push(y);
        }
    }
    priority_queue< pair<int,int> > q2;
    for(int i=1;i<=n;i++){
        if(!ind[i]){
            q2.push({-fmx[i],i});
        }
    }
    while(!q2.empty()){
        int x=q2.top().second;
        q2.pop();
        if(a[x]==0){
            auto it=st.lower_bound(fmn[x]);
            if(it!=st.end() && (*it)<=fmx[x]){
                a[x]=*it;
                st.erase(it);
            }
            else{
                puts("-1");
                return ;
            }
        }
        for(auto y:G[x]){
            ind[y]--;
            if(!ind[y]) q2.push({-fmx[y],y});
        }
    }
    for(int i=1;i<=n;i++) printf("%d ",a[i]);
    printf("\n");
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        solve();
    }
    return 0;
}

Source code, Language: C++23