Submission #306468

#	Time	Username	Problem	Language	Result	Execution time	Memory
306468		jungsnow	JOIRIS (JOI16_joiris)	C++14	100 / 100	5 ms	896 KiB

joiris

#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 / 15
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 55 / 55