[Codeforces] Codeforces Round #669 (Div. 2) A. Ahahahahahahahaha

2020年9月9日2020年12月13日

問題

方針

配列 \( a \) から並びを変えずに \( \dfrac{n}{2} \) 個以上要素を選んだ配列を \( b \) としたとき、\( b \) が \( b \) の奇数番目の和と偶数番目の和が等しくなるようにします。

\( a \) の \( 0 \) の個数が \( \dfrac{n}{2} \) 以上のとき

このとき、\( \dfrac{n}{2} \) 個の \( 0 \) を出力します。

\( a \) の \( 0 \) の個数が \( \dfrac{n}{2} \) 未満のとき

\( \dfrac{n}{2} \bmod 2 = 0 \) のとき

このとき、\( \dfrac{n}{2} \) 個の \( 1 \) を出力します。

\( \dfrac{n}{2} \bmod 2 = 1 \) のとき

このとき、\( \dfrac{n}{2} + 1\) 個の \( 1 \) を出力します。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int a[100000];

void solve(int n) {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] == 0) cnt++;
    }
    
    if (cnt >= n / 2) {
        cout << n / 2 << "\n";
        for (int i = 0; i < n / 2; i++) {
            if (i == n / 2 - 1) {
                cout << "0\n";
            } else {
                cout << "0 ";
            }
        }
    } else {
        if ((n / 2) % 2 == 0) {
            cout << n / 2 << "\n";
            for (int i = 0; i < n / 2; i++) {
                if (i == n / 2 - 1) {
                    cout << "1\n";
                } else {
                    cout << "1 ";
                }
            }
        } else {
            cout << n / 2 + 1 << "\n";
            for (int i = 0; i < n / 2 + 1; i++) {
                if (i == n / 2) {
                    cout << "1\n";
                } else {
                    cout << "1 ";
                }
            }
        }

    }
}

int main() {
    int t, n;
    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> n;
        for (int j = 0; j < n; j++) {
            cin >> a[j];
        }
        solve(n);
    }
    return 0;
}