oj.uz

Submission #948669

# Submission time Handle Problem Language Result Execution time Memory
948669 2024-03-18T10:21:52 Z Pring JOIRIS (JOI16_joiris) C++17
15 / 100
 1 ms 608 KB 
#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 MOVE() {
        int pos = [&]() -> int {
            FOR(i, 1, n + 1) if (b[i]) return i;
            return 0;
        }();
        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) if (!b[i]) {
            b[i + 1] = true;
            b[i] = true;
            ans.emplace_back(2, i);
        }
        REVERSE();
    }

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

Compilation message

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 600 KB Output is correct
12 Correct 0 ms 456 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 608 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 600 KB Output is correct
12 Correct 0 ms 456 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 608 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Incorrect 0 ms 348 KB Unexpected end of file - int32 expected
18 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 600 KB Output is correct
12 Correct 0 ms 456 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 608 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Incorrect 0 ms 348 KB Output isn't correct
18 Halted 0 ms 0 KB -