Parititon the numbers [CodeChef January Challenge 2018 E]

https://www.codechef.com/JAN18/problems/PRTITION

1～Nの数が1つずつある。
この中でxだけ除外する。
残った数を2グループに分け、各グループの総和が等しくなるように出来るか求めよ。
等しく出来ないならImpossible、出来るなら、どのように分けるかを示せ。
テストケース数は最大10^5

解法

テストケースの量が10^5ということは1テストならしO(1)かO(logN)くらいで解く必要がある。
この時点で何か法則を見つけないとやばそうな感じが伝わってくるので実験しよう。
　

• N=2 なし
• N=3 なし
• N=4 x=2,4
• N=5 x=1,3,5
• N=6 x=1,3,5
• N=7 x=2,4,6

　
残った数を2グループに分けて同じ数ということは、残った数の総和は最低限偶数になる必要がある。
4≦Nの場合は残りの総和が偶数となれば作れている。
なので、未証明ではあるが、残りの総和が偶数ならば作れると仮定して実装する。
作れるかどうかの判定はこれでOKなので、あとは、どのように分けるかである。
　
これも微妙に適当に出来るのではないかという仮定の元、大きい方から貪欲にとっていく。
貪欲にやってみると落ちたので、見てみるとxが1か2の場合はうまくいかない場合がある。
　
これを直そうと、考えてみるが、サボって適当にやっても通るんじゃないかと、最大Nを抜かして同様の貪欲をやると通る。

typedef long long ll;
//---------------------------------------------------------------------------------------------------
void solve(int X, int N) {
    ll sm = 0;
    rep(i, 1, N + 1) if (i != X) sm += i;
    if (N <= 3 or sm % 2 == 1) {
        printf("impossible\n");
        return;
    }

    ll rest = sm / 2;
    string ans = "";
    rrep(i, N, 1) {
        if (i == X) {
            ans += "2";
            continue;
        }

        if (i <= rest) {
            rest -= i;
            ans += "1";
        }
        else ans += "0";
    }
    reverse(ans.begin(), ans.end());

    if (rest != 0) {
        rest = sm / 2;
        ans = "0";
        rrep(i, N - 1, 1) {
            if (i == X) {
                ans += "2";
                continue;
            }

            if (i <= rest) {
                rest -= i;
                ans += "1";
            }
            else ans += "0";
        }
        reverse(ans.begin(), ans.end());
    }

    printf("%s\n", ans.c_str());
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) {
        int X, N;
        cin >> X >> N;
        solve(X, N);
    }
}