제출 #948688

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
948688		Pring	JOIRIS (JOI16_joiris)	C++17	30 / 100	1 ms	844 KiB

joiris

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

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

const int MXN = 55;
int n, k, a[MXN];
vector<pii> ans;
bitset<MXN> b;

int find_fs() {
    FOR(i, 1, n + 1) if (b[i]) return i;
    return 0;
}

void FILL() {
    int big = *max_element(a + 1, a + n + 1);
    FOR(i, 1, n + 1) {
        while (a[i] + 2 <= big) {
            ans.emplace_back(1, i);
            a[i] += 2;
        }
    }
    int sml = *min_element(a + 1, a + n + 1);
    FOR(i, 1, n + 1) {
        a[i] -= sml;
        if (a[i]) b[i] = true;
    }
}

bool sweep() {
    bitset<MXN> c;
    vector<int> v;
    FOR(i, 1, n + 1) if (b[i]) v.push_back(i);
    if (v.empty()) return false;
    for (int i = 0; i < v.size() - 1; i++) {
        if (v[i] % 2 != v[i + 1] % 2) {
            int l = v[i], r = v[i + 1];
            for (int i = l + 1; i < r; i += 2) ans.emplace_back(2, i);
            for (int i = l; i < r; i += 2) ans.emplace_back(2, i);
            FOR(j, l, r + 1) c[j] = true;
            b[l] = false;
            b[r] = false;
            a[l]--;
            a[r]--;
            i++;
        }
    }
    if (c.count() == 0) return false;
    FOR(i, 1, n + 1) if (!c[i]) ans.emplace_back(1, i);
    return true;
}

void REVERSE() {
    FOR(i, 1, n + 1) {
        b[i] = !b[i];
        if (b[i]) ans.emplace_back(1, i);
    }
}
void COUT() {
    cout << ans.size() << '\n';
    for (auto &i : ans) cout << i.fs << ' ' << i.sc << '\n';
}

namespace SB1 {

    void PARITY(int n, bool f) {
        FOR(i, 1, n + 1) a[i] = b[i];
        if (f) {
            ans.emplace_back(1, n);
            a[n] += 2;
            n--;
        }
        int pos = find_fs();
        FOR(i, 1, pos + 1) {
            ans.emplace_back(1, i);
            a[i] += 2;
        }
        for (int i = pos + 2; i <= n; i += 2) {
            if (b[i]) {
                ans.emplace_back(2, i - 1);
                a[i - 1]++;
                a[i]++;
            } else {
                ans.emplace_back(1, i - 1);
                ans.emplace_back(1, i);
                a[i - 1] += 2;
                a[i] += 2;
            }
        }
        if (f) n++;
        FOR(i, 1, n + 1) {
            if (i == pos) continue;
            ans.emplace_back(1, i);
            a[i] += 2;
        }
        auto sml = *min_element(a + 1, a + n + 1);
        FOR(i, 1, n + 1) {
            a[i] -= sml;
            if (a[i]) b[i] = true;
            else b[i] = false;
        }
    }

    void solve() {
        if (b.count() % 2) {
            cout << -1 << '\n';
            return;
        }
        while (sweep());
        if (b.count() == 0) {
            COUT();
            return;
        }
        if ([&]() -> bool {
            FOR(i, 1, n + 1) if (b[i]) return (i & 1);
            return 0;
        }()) {
            REVERSE();
            while (sweep());
        }
        while (b.count()) {
            PARITY(n, false);
            while (sweep());
        }
        COUT();
    }
}

namespace SB2 {

    void MOVE() {
        int pos = find_fs();
        for (int i = pos + 2; i <= n; i += 2) if (!b[i]) {
            b[i - 1] = true;
            b[i] = true;
            ans.emplace_back(2, i - 1);
        }
        for (int i = 1; i < pos; i += 2) {
            b[i + 1] = true;
            b[i] = true;
            ans.emplace_back(2, i);
        }
        REVERSE();
    }

    void TRANSFORM() {
        int pos = find_fs();
        b[pos - 1] = 1;
        b[pos] = 0;
        FOR(i, 1, n + 1) {
            if (i == pos - 1) continue;
            if (i == pos) continue;
            ans.emplace_back(1, i);
        }
        ans.emplace_back(2, pos - 1);
        ans.emplace_back(1, pos - 1);
    }

    void solve() {
        while (sweep());
        if (b.count() == 0) {
            COUT();
            return;
        }
        if (find_fs() & 1) {
            MOVE();
        }
        while (b.count() > 1) {
            TRANSFORM();
            while (sweep());
        }
        if (b.count() == 1) {
            TRANSFORM();
            int pos = [&]() -> int {
                FOR(i, 1, n + 1) if (b[i]) return i;
                return 0;
            }();
            for (int i = 1; i < pos; i += 2) ans.emplace_back(2, i);
            for (int i = pos + 1; i <= n; i += 2) ans.emplace_back(2, i);
        }
        COUT();
    }
}

void miku() {
    cin >> n >> k;
    FOR(i, 1, n + 1) cin >> a[i];
    if (k > 2) return;
    FILL();
    if (n & 1) SB2::solve();
    else SB1::solve();
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

joiris.cpp: In function 'bool sweep()':
joiris.cpp:51:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (int i = 0; i < v.size() - 1; i++) {
      |                     ~~^~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 55