oj.uz

Submission #306468

# Submission time Handle Problem Language Result Execution time Memory
306468 2020-09-25T15:57:24 Z jungsnow JOIRIS (JOI16_joiris) C++14
100 / 100
 5 ms 896 KB 
#include<bits/stdc++.h>
#define x first
#define y second
#define bug(x) cerr<<#x<<" = "<<x<<'\n'

using namespace std;

typedef pair <int, int> ii;

const int N = 1005;

int n, k, a[N], b[N];
bool tab[5 * N][N];
vector <ii> ans;

void ver(int x) {
    ans.push_back({1, x + 1});
    for (int j = 1; j <= k; ++j) {
        tab[a[x] + j][x] = 1;
    }
    a[x] += k;
    return;
}

void hor(int x) {
    if (x < k - 1) return;
    ans.push_back({2, x - k + 2});
    int base = 0;
    for (int i = 0; i < k; ++i)
        base = max(base, a[x - i]);
    base++;
    for (int i = 0; i < k; ++i) {
        a[x - i] = base;
        tab[base][x - i] = 1;
    }
    return;
}

bool del(int x) {
    for (int i = 0; i < n; ++i)
        if (tab[x][i] == 0) return 0;
    for (int i = 0; i < n; ++i) {
        for (int j = x; j <= a[i]; ++j) {
            tab[j][i] = tab[j + 1][i];
        }
        bool has = 0;
        for (int j = a[i]; j >= 0; --j) {
            if (tab[j][i]) {
                has = 1;
                a[i] = j;
                break;
            }
        }
        if (!has) a[i] = 0;
    }
    return 1;
}

void check() {
    int ma = 0;
    for (int i = 0; i < n; ++i) ma = max(ma, a[i]);
    for (int i = 1; i <= ma; ++i)
        while (del(i));
}

void show() {
    for (int i = 0; i < n; ++i) {
        cerr << a[i] << '\n';
        for (int j = 1; j <= 7; ++j) {
            cerr << tab[j][i];
        }
        cerr << '\n';
    }
    cerr<<'\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("cc.inp", "r", stdin);
//    freopen("cc.out", "w", stdout);
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        for (int j = 1; j <= a[i]; j++)
            tab[j][i] = 1;
        b[i % k] += a[i];
        b[i % k] %= k;
    }
    int m = n % k;
//    for (int i = 0; i < k; ++i)
//        bug(b[i]);
    for (int i = 0; i < m; ++i) {
        if (b[i] % k != b[0] % k) {
            cout << -1;
            return 0;
        }
    }
    for (int i = m; i < k; ++i) {
        if (b[i] % k != b[k - 1] % k) {
            cout << -1;
            return 0;
        }
    }
    check();

    ///step - 1
    for (int i = 1; i < n; ++i)
        while (a[i] < a[i - 1])
            ver(i);
    check();

    ///step - 2
    for (int i = 1; i <= a[n - 1]; ++i) {
        int r = 0;
        for (r = 0; r < n; ++r)
            if (a[r] >= i) break;
        --r;
        while (r >= k - 1) {
            hor(r);
            r -= k;
        }
    }
    check();

    ///step - 3
    for (int i = 0; i < k - 1; ++i) {
        int ma = 0;
        for (int j = i; j < n; ++j)
            ma = max(ma, a[j]);
        while (a[i] < ma) ver(i);
        check();
    }

    ///step - 4
    int base = 0;
    for (int i = m; i < k - 1; ++i)
        base = max(base, a[i]);
    for (int i = m; i < k - 1; ++i)
        while (a[i] < base) ver(i);
    for (int i = 0; i < m; ++i)
        while (a[i] < base) ver(i);
    check();

    ///step - 5
    base = 0;
    for (int i = 0; i < m; ++i) base = max(base, a[i]);
    for (int i = 0; i < m; ++i)
        while (a[i] < base) ver(i);
    for (int i = 0; i < base; ++i) {
        for (int j = m; j < n; j += k)
            hor(j + k - 1);
    }

    ///cout
    cout << (int)ans.size() << '\n';
    for (ii e : ans) {
        cout << e.x << ' ' << e.y << '\n';
    }
}

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
15.0 / 15.0

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

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 1 ms 384 KB Output is correct
33 Correct 1 ms 512 KB Output is correct
34 Correct 1 ms 384 KB Output is correct
35 Correct 1 ms 512 KB Output is correct
36 Correct 1 ms 384 KB Output is correct
37 Correct 1 ms 384 KB Output is correct
38 Correct 1 ms 384 KB Output is correct
39 Correct 1 ms 640 KB Output is correct
40 Correct 1 ms 512 KB Output is correct
41 Correct 4 ms 896 KB Output is correct
42 Correct 1 ms 384 KB Output is correct
43 Correct 1 ms 512 KB Output is correct
44 Correct 1 ms 384 KB Output is correct
45 Correct 1 ms 512 KB Output is correct
46 Correct 1 ms 384 KB Output is correct
47 Correct 1 ms 384 KB Output is correct
48 Correct 1 ms 384 KB Output is correct
49 Correct 1 ms 384 KB Output is correct
50 Correct 1 ms 384 KB Output is correct
51 Correct 1 ms 384 KB Output is correct
52 Correct 1 ms 384 KB Output is correct
53 Correct 1 ms 384 KB Output is correct
54 Correct 1 ms 384 KB Output is correct
55 Correct 1 ms 384 KB Output is correct
56 Correct 1 ms 384 KB Output is correct
57 Correct 1 ms 384 KB Output is correct
58 Correct 1 ms 384 KB Output is correct
59 Correct 1 ms 404 KB Output is correct
60 Correct 1 ms 384 KB Output is correct
61 Correct 1 ms 384 KB Output is correct
62 Correct 1 ms 384 KB Output is correct
63 Correct 1 ms 512 KB Output is correct
64 Correct 1 ms 512 KB Output is correct
65 Correct 1 ms 512 KB Output is correct
66 Correct 1 ms 384 KB Output is correct
67 Correct 1 ms 384 KB Output is correct
68 Correct 1 ms 384 KB Output is correct
69 Correct 1 ms 384 KB Output is correct
70 Correct 1 ms 512 KB Output is correct
71 Correct 2 ms 768 KB Output is correct
72 Correct 3 ms 768 KB Output is correct
73 Correct 3 ms 768 KB Output is correct
74 Correct 2 ms 640 KB Output is correct
75 Correct 1 ms 512 KB Output is correct
76 Correct 1 ms 512 KB Output is correct
77 Correct 1 ms 384 KB Output is correct
78 Correct 1 ms 384 KB Output is correct
79 Correct 1 ms 384 KB Output is correct
80 Correct 1 ms 384 KB Output is correct
81 Correct 5 ms 896 KB Output is correct
82 Correct 1 ms 384 KB Output is correct
83 Correct 1 ms 384 KB Output is correct
84 Correct 1 ms 512 KB Output is correct
85 Correct 1 ms 384 KB Output is correct
86 Correct 1 ms 384 KB Output is correct
87 Correct 0 ms 384 KB Output is correct
88 Correct 1 ms 384 KB Output is correct
89 Correct 0 ms 384 KB Output is correct
90 Correct 1 ms 384 KB Output is correct
91 Correct 1 ms 384 KB Output is correct
92 Correct 1 ms 384 KB Output is correct