1562: [NOI2009]变换序列

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 2139  Solved: 1079
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

5
1 1 2 2 1

Sample Output

1 2 4 0 3

HINT

30%的数据中N≤50；
60%的数据中N≤500；
100%的数据中N≤10000。

Source

 

[ Submit][ Status][ Discuss]

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000+5;

bool vis[maxn];
int a,n;
int whi[maxn],p[maxn][2];
int w[maxn];

bool dfs(int x)
{
    if(x==-1)
        return false;
    for(int i=0;i<2;i++)
    {
        if(!vis[p[x][i]])
        {
            vis[p[x][i]]=true;
            if(whi[p[x][i]]==-1||dfs(whi[p[x][i]]))
            {
                w[x]=p[x][i];
                whi[p[x][i]]=x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a);
        p[i][0]=min((a+i)%n,(n-a+i)%n);
        p[i][1]=max((a+i)%n,(n-a+i)%n);
    }
    memset(whi,-1,sizeof whi);
    for(int i=n-1;i>=0;i--)
    {
        memset(vis,false,sizeof vis);
        if(!dfs(i))
        {
            printf("No Answer\n");
            return 0;
        }
    }
    for(int i=0;i<n;i++)
    {
        if(i==n-1)
            printf("%d\n",w[i]);//这个鬼畜输出害我半天格式错误，最后一个输出不能有空格！ 
        else
            printf("%d ",w[i]);
    }
    return 0;
}