Submission #948617

#	Time	Username	Problem	Language	Result	Execution time	Memory
948617		Pring	JOIRIS (JOI16_joiris)	C++17	15 / 100	1 ms	460 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;

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 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 = [&]() -> int {
        FOR(i, 1, n + 1) if (b[i]) return i;
        return 0;
    }();
    debug(pos);
    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;
    }
    // FOR(i, 1, n + 1) cout << b[i];
    // cout << endl;
}

void COUT() {
    cout << ans.size() << '\n';
    for (auto &i : ans) cout << i.fs << ' ' << i.sc << '\n';
}

namespace SB1 {

    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 TRANSFORM() {
        int pos = [&]() -> int {
            FOR(i, 1, n + 1) if (b[i]) return i;
            return 0;
        }();
        FOR(i, 1, n + 1) b[i] = 1;
        b[pos - 1] = 0;
        FOR(i, 1, pos - 1) ans.emplace_back(1, i);
        ans.emplace_back(2, pos - 1);
    }

    void solve() {
        while (sweep());
        if ([&]() -> bool {
            FOR(i, 1, n + 1) if (b[i]) return (i & 1);
            return 0;
        }()) {
            REVERSE();
            while (sweep());
        }
        if (b.count() == 0) {
            COUT();
            return;
        }
        while (b.count() > 1) {
            PARITY(n, true);
            while (sweep());
        }
        if (b.count() == 0) {
            COUT();
            return;
        }
        TRANSFORM();
        FILL();
        COUT();
    }
}

void miku() {
    cin >> n >> k;
    FOR(i, 1, n + 1) cin >> a[i];
    if (k > 2) return;
    FILL();
    // cout << "PRING" << endl;
    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;
}

Compilation message (stderr)

joiris.cpp: In function 'bool sweep()':
joiris.cpp:46: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]
   46 |     for (int i = 0; i < v.size() - 1; i++) {
      |                     ~~^~~~~~~~~~~~~~
joiris.cpp: In function 'void PARITY(long long int, bool)':
joiris.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
joiris.cpp:82:5: note: in expansion of macro 'debug'
   82 |     debug(pos);
      |     ^~~~~

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