记录编号	29031	评测结果	AAAAAAAAAA
题目名称	[NOI 2009]变换序列	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.036 s
提交时间	2011-10-19 19:45:01	内存使用	0.26 MiB

#include <cstdio>
#include <bitset>

using namespace std;

typedef int way_t[2];

int N;
way_t *way;
int *mat, *rmat;
bitset<10001> boo;

bool path (const int wh)
{
    int i = -1;
    while (++i < 2)
        if (!boo[way[wh][i]])
        {
            boo[way[wh][i]] = 1;
            if (mat[way[wh][i]] == 0 ||
                    path(mat[way[wh][i]]))
            {
                mat[way[wh][i]] = wh;
                rmat[wh] = way[wh][i];
                return true;
            }
        }

    return false;
}

int main ()
{
    freopen("transform.in", "r", stdin);
    freopen("transform.out", "w", stdout);

    scanf("%d", &N);
    mat = new int[N];
    rmat = new int[N];
    way = new way_t[N];

    for (int i=0; i<=N; i++)
    {
        int a;
        scanf("%d", &a);

        way[i][0] = (i-a)>=0 ? i-a : i-a+N,
        way[i][1] = (i+a)>=N ? i+a-N : i+a;

        if (way[i][0] > way[i][1])
        {
            int t = way[i][0];
            way[i][0] = way[i][1];
            way[i][1] = t;
        }
        else if (way[i][0] == way[i][1])
            way[i][1] = N;

    }

    int ct = 0;
    for (int i=N-1; i>=0; i--)
    {
        boo.reset();
        boo[N] = 1;
        if (path(i))
            ct++;
    }

    if (ct == N)
    {
        for (int i=0; i<N; i++)
            printf("%d ", rmat[i]);
        putchar('\n');
    }
    else
        puts("No Answer\n");

    return 0;
}