oj.uz

Submission #165514

# Submission time Handle Problem Language Result Execution time Memory
165514 2019-11-27T11:49:00 Z dolphingarlic JOIRIS (JOI16_joiris) C++14
30 / 100
 18 ms 504 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int a[50], b[50], c[50];
vector<pair<int, int>> moves;
// {1, x} = Vertical
// {2, x} = Horizontal

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    FOR(i, 0, n) {
        cin >> a[i];
        b[i % k] = (b[i % k] + a[i]) % k;
    }

    // Checks if possible
    FOR(i, 1, n % k) if (b[i] != b[i - 1]) return cout << -1, 0;
    FOR(i, n % k + 1, k) if (b[i] != b[i - 1]) return cout << -1, 0;

    // Makes heights non-decreasing from left to right
    FOR(i, 1, n) {
        while (a[i] < a[i - 1]) {
            moves.push_back({1, i});
            a[i] += k;
        }
    }
    FOR(i, 0, n) c[i] = a[i];

    // Places horizontal blocks to make rows k-1 to n-1 equal
    FOR(i, 0, a[n - 1]) {
        int pos = upper_bound(a, a + n, i) - a - 1;
        while (pos >= k - 1) {
            FOR(j, pos - k + 1, pos + 1) c[j]++;
            moves.push_back({2, pos - k + 1});
            pos -= k;
        }
    }

    // Places vertical blocks to make rows k-1 to n-1 equal to 0
    FOR(i, 0, k - 1) {
        while (c[i] < c[n - 1]) {
            moves.push_back({1, i});
            c[i] += k;
        }
    }

    // Places vertical blocks to make rows n%k to k-2 equal to 0
    int mx = *max_element(c + n % k, c + k - 1);
    FOR(i, n % k, k - 1) {
        while (c[i] != mx) {
            moves.push_back({1, i});
            c[i] += k;
        }
    }

    // Places vertical and horizontal blocks to clear the board
    mx = *max_element(c, c + n % k);
    FOR(i, 0, n % k) {
        while (c[i] != mx) {
            moves.push_back({1, i});
            c[i] += k;
        }
    }
    FOR(i, 0, c[0] - c[n % k]) moves.push_back({2, n % k});


    cout << moves.size() << '\n';
    for (pair<int, int> i : moves) cout << i.first << ' ' << i.second + 1 << '\n';
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 15.0

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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 3 ms 504 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 380 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 2 ms 376 KB Output is correct
29 Correct 2 ms 376 KB Output is correct
30 Correct 2 ms 376 KB Output is correct
31 Correct 2 ms 376 KB Output is correct
32 Correct 2 ms 376 KB Output is correct
33 Correct 2 ms 376 KB Output is correct
34 Correct 2 ms 376 KB Output is correct
35 Correct 2 ms 376 KB Output is correct
36 Correct 3 ms 376 KB Output is correct
37 Correct 2 ms 376 KB Output is correct
38 Correct 2 ms 376 KB Output is correct

Subtask #4
0 / 55.0

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