oj.uz

답안 #948688

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
948688 2024-03-18T11:06:43 Z Pring JOIRIS (JOI16_joiris) C++17
30 / 100
 1 ms 844 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;

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;
}

Compilation message

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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 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 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 0 ms 460 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 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 0 ms 348 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 1 ms 456 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 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 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 0 ms 460 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 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 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 0 ms 460 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 844 KB Output is correct
25 Correct 1 ms 456 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 1 ms 344 KB Output is correct
33 Incorrect 0 ms 348 KB Unexpected end of file - int32 expected
34 Halted 0 ms 0 KB -