QOJ.ac

QOJ

ID	提交记录ID	题目	Hacker	Owner	结果	提交时间	测评时间
#996	#641108	#6817. Permutation Puzzle	czc	czc	Success!	2024-10-14 18:36:13	2024-10-14 18:36:14

詳細信息

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	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#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;
}

源文件, 语言: C++23