6496 - Cyclic antimonotonic permutations

문제 번역

다음 조건을 만족하는 길이가 $N$이고 1에서 $N$까지로 이루어 진 순열을 만들어야 합니다. 

1. 반단조성 : 인접한 세 수를 보았을 때 가운데 수가 가장 크거나 가장 작아야 합니다.
2. 사이클 : $i$번째에 있는 수 $p_i$를 $i$에서 $p_i$로 가는 포인터로 생각합시다. 1에서부터 시작해서 포인터를 따라가면 모든 위치를 다 방문하고 다시 1로 돌아와야 합니다.

step 1

홀수 번째에서 1부터 $\lceil n/2 \rceil$까지, 짝수 번째에는 나머지가 들어온다고 생각합니다(홀짝이 반대여도 됩니다). 그럼 첫 번째 조건은 알아서 만족합니다.

step 2

$N$이 짝수인 경우 먼저 생각해 봅시다. $N$이 4인 경우는 손으로 만들 수 있습니다.(2 4 1 3)

$N$개일때의 답을 알고 있을 때, $N+2$일 때의 답을 알아내 봅시다.

 

모든 숫자를 1 증가시키고 앞뒤에 빈 칸을 만들어 줍니다. 그럼 사이클이 유지되고 step1에서 말한 조건도 만족합니다(이때, 홀짝이 바뀌게 됩니다).

이제 뒤에 1, 앞에 $N$을 넣어줍니다. 1번 조건은 완벽히 만족했습니다. 이 상태에서 2번을 어떻게 만족시켜 줄까요?

 

step 3

어떤 두 사이클이 있을 때 각 사이클에서 원소 하나씩 뽑아 바꿔주면 두 사이클이 하나로 합쳐집니다.

아래와 같은 사이클을 생각해 봅시다. 정점 밖에 있는 숫자가 정점의 번호, 원 안에 있는 숫자는 목적지입니다.

3번 정점과 7번 정점의 값을 바꾸면 하나로 합쳐집니다. 이것은 어떤 정점을 골라도 같습니다.

원래 문제로 돌아와 봅시다. 1번 조건에 만족하도록 아무 두 값을 바꿔주면 됩니다. 저는 1번과 3번 을 바꿔주었습니다.

이것을 계속 해 주면 해결할 수 있습니다. 이때, 홀짝이 계속 바뀌는 것을 신경써 줍니다.

step 4

홀수는 살짝 다릅니다. 앞뒤로 2개씩 추가해 줍니다. 4로 나눈 나머지가 3인 경우와 1인 경우로 구분해 생각해야 합니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
int b[4000000];
int main() {
    int n, i,s,e,base,t;
    while (1) {
        scanf("%d", &n);
        if (n == 0) break;
        if (n % 2 == 0) {
            s = 2000000; e = 2000003;
            b[s] = 3;
            b[s + 1] = 1;
            b[s + 2] = 4;
            b[s + 3] = 2;
            base = 1;
            t = 1;
            for (i = 6;i <= n;i += 2) {
                s--; e++;
                base--;
                if (t == 1) {
                    b[s] = base;
                    b[e] = base + i - 1;
                    swap(b[s], b[s + 2]);
                    swap(b[e], b[e - 2]);
                    t = 0;
                }
                else {
                    b[e] = base;
                    b[s] = base + i - 1;
                    swap(b[s], b[s + 2]);
                    t = 1;
                }
            }
        }
        else if(n%4==3){
            s = 2000000; e = 2000002;
            b[s] = 2;
            b[s + 1] = 3;
            b[s + 2] = 1;
            base = 1;
            t = 1;
            for (i = 7;i <= n;i += 4) {
                s-=2; e+=2;
                base-=2;
                b[s] = base + 1;
                b[s + 1] = base + i - 2;
                b[e] = base;
                b[e - 1] = base + i - 1;
                swap(b[s], b[s + 2]);
            }
        }
        else {
            s = 2000000; e = 2000004;
            b[s] = 2;
            b[s + 1] = 4;
            b[s + 2] = 1;
            b[s + 3] = 5;
            b[s + 4] = 3;
            base = 1;
            t = 1;
            for (i = 9;i <= n;i += 4) {
                s -= 2; e += 2;
                base -= 2;
                b[s] = base + 1;
                b[s + 1] = base + i - 2;
                b[e] = base;
                b[e - 1] = base + i - 1;
                swap(b[s], b[s + 2]);
            }
        }
        for (i = s;i <= e;i++) {
            printf("%d ", b[i] + (-base + 1));
        }
        printf("\n");
    }
    return 0;
}