1 条题解

  • 1
    @ 2022-8-29 9:44:12
    #include<bits/stdc++.h>
    using namespace std;
    #define il inline
    #define re register
    #define debug printf("Now is Line : %d\n",__LINE__)
    il int read()
    {
        re int x=0,f=1; re char c=getchar();
        while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
        while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
        return x*f;
    }
    #define maxn 10005
    int n,m,d[maxn],aa[2][maxn],vis[maxn],cnt,ans,match[maxn],to[maxn];
    bool dfs(int u)
    {
        for(re int i=0;i<2;++i)
        {
            int v=aa[i][u];
            if(vis[v]) continue;
            vis[v]=1;
            if(match[v]==-1||dfs(match[v])) return match[v]=u,to[u]=v,1;
        }
        return 0;
    }
    int main()
    {
        n=read();
        memset(match,-1,sizeof(match));
        for(re int i=0;i<n;++i) d[i]=read();
        for(re int i=0;i<n;++i)
        {
            int a=(i-d[i]+n)%n,b=(i+d[i])%n;
            if(a>b) swap(a,b);
            aa[0][i]=a,aa[1][i]=b;
        }
        for(re int i=n-1;~i;--i)
        {
            memset(vis,0,sizeof(vis));
            if(dfs(i)) ++ans;
        }
        if(ans<n) return puts("No Answer"),0;
        for(re int i=0;i<n;++i) printf("%d ",to[i]);
        return 0;
    }
    
    • 1

    信息

    ID
    1562
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    (无)
    递交数
    10
    已通过
    7
    上传者