Codeforces Round #640 (Div. 4) G. Special Permutation

May 14, 2020

競技プログラミング

Codeforces, 構築

問題

問題リンク

数値n (>= 2)が与えられるので、1~nまでの数列を作れ
条件として、数列のi番目とi+1番目の差の絶対値が2以上4以下であること
作れない場合は-1を出力し、作れる場合は実際にそれを表示すること

考えたこと

小さい数値で実際に作ってみる

n == 2,3の場合はどんなに頑張っても作れない
n == 4の場合は{2,4,1,3}で作れる
n == 5の場合は{1,3,5,2,4}
n == 6の場合は{1,4,2,6,3,5}
n == 7の場合は{1,4,2,5,7,3,6}
n == 8の場合は{2,4,1,3,6,8,5,7}

これをみると、n==4のパターンが繰り返せそうに見える
実際にn==8は{2,4,1,3,2+4,4+4,1+4,3+4}とも言える

あらかじめn=4~7のパターンを定義しておいて、以下のように場合分けすればいけそう

n == 2,3の場合は-1を出力
n < 8の場合は上記のパターンを出力
n >= 8の場合は、div = n/4とrem = n%4の値を求めておき, n==4のパターンをdiv-1回繰り返した後に、最後の1パターンをn == rem+4のパターンで作れば良さそう

あとはこれを実装する

実装

int main() {
    vector<vector<int>> ptn(10);
    ptn[4] = {2,4,1,3};
    ptn[5] = {1,3,5,2,4};
    ptn[6] = {1,4,2,6,3,5};
    ptn[7] = {1,4,2,5,7,3,6};

    int t; cin >> t;
    rep(_, t) {
        int n; cin >> n;
        if(n == 2 || n == 3) {
            cout << -1;
        } else if(n < 8) {
            rep(i, ptn[n].size()) {
                cout << ptn[n][i];
                if(i != ptn[n].size()-1) cout << " ";
            }
        } else {
            int rem = n % 4;
            int div = n / 4;
            int now = 0;
            rep(__, div-1) {
                rep(i, 4) {
                    cout << ptn[4][i] + now << " ";
                }
                now += 4;
            }
            rep(i, ptn[rem+4].size()) {
                cout << ptn[rem+4][i] + now;
                if(i != ptn[rem+4].size()-1) cout << " ";
            }
        }
        cout << endl;
    }

    return 0;
}