oj.uz

Submission #553327

# Submission time Handle Problem Language Result Execution time Memory
553327 2022-04-25T12:59:23 Z RaresFelix JOIRIS (JOI16_joiris) C++17
30 / 100
 4 ms 580 KB 
#include <bits/stdc++.h>

using namespace std;
int n, k;
int main() {
    cin.tie(0);
    cin >> n >> k;
    vector<int> V(n + 1), R(k);
    for(int i = 1; i <= n; ++i) cin >> V[i], R[(i - 1) % k] = (R[(i - 1) % k] + V[i]) % k;
    int ok = 1;
    for(int i = 0; i < n % k - 1; ++i)
        ok &= R[i] == R[i + 1];
    for(int i = n % k; i < k - 1; ++i)
        ok &= R[i] == R[i + 1];
    if(!ok) {
        cout << "-1\n";
        return 0;
    }
    vector<pair<int, int> > Sol;
    function<void(bool)> level = [&](auto flag) {
        int ma = 0;
        for(int i = 1; i <= n; ++i)
            ma = max(ma, V[i]);
        for(int i = 1; i <= n; ++i)
            while(V[i] + k <= ma) Sol.push_back({1, i}), V[i] += k;
        int mi = ma;
        for(int i = 1; i <= n; ++i)
            mi = min(mi, V[i]);
        for(int i = 1; i <= n; ++i) V[i] -= mi;
        if(flag) {
            mi = k + 1;
            for(int i = 1; i <= n; ++i) {
                V[i] -= V[n];
                mi = min(mi, V[i]);
            }
            if(mi < 0)
                for(int i = 1; i <= n; ++i)
                    if(V[i] < 0)
                        Sol.push_back({1, i}), V[i] += k;
        }
    };
    auto add_one = [&](auto poz) {
        Sol.push_back({2, poz - k + 1});
        for(int i = 1; i <= n; ++i)
            if(i < poz - k + 1 || i > poz) Sol.push_back({1, i}), V[i] += k - 1;
        level(1);
    };
    level(0);
    auto swap_one = [&]() {
        for(int i = n; i >= k; i -= k) add_one(i);
    };
    auto solved = [&]() {
        for(int i = 1; i <= n; ++i) if(V[i]) return false;
        return true;
    };
    auto clean = [&]() {
        for(int i = n; i >= k; --i) {
            int d = V[i];
            for(int j = 1; j <= (k - d) % k; ++j)
                add_one(i);
        }
    };
    clean();
    while(!solved()) {
        swap_one();
        for(int i = 1; !solved() && i <= k; ++i)
            clean();
    }
    cout << Sol.size() << "\n";
    for(auto [a, b] : Sol) cout << a << " " << b << "\n";
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 300 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 296 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 340 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 304 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 304 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 300 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 296 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 0 ms 312 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 312 KB Output is correct
23 Correct 2 ms 428 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Incorrect 4 ms 580 KB Integer 12907 violates the range [-1, 10000]
26 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 300 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 296 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 0 ms 304 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 1 ms 304 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 0 ms 312 KB Output is correct
37 Correct 1 ms 212 KB Output is correct
38 Correct 1 ms 312 KB Output is correct
39 Correct 2 ms 428 KB Output is correct
40 Correct 1 ms 340 KB Output is correct
41 Incorrect 4 ms 580 KB Integer 12907 violates the range [-1, 10000]
42 Halted 0 ms 0 KB -