Submission #404471

#TimeUsernameProblemLanguageResultExecution timeMemory
404471timmyfengJOIRIS (JOI16_joiris)C++17
100 / 100
3 ms372 KiB
#include <bits/stdc++.h>
using namespace std;

const int N = 52;

int work[N], diff[N];
int a[N], n, k;

vector<array<int, 2>> ans;

void clear() {
    int mini = *min_element(a + 1, a + 1 + n);
    for (int i = 1; i <= n; ++i) {
        a[i] -= mini;
    }
}

void normalize() {
    clear();

    while (*max_element(a + 1, a + 1 + n) >= k) {
        int i = min_element(a + 1, a + 1 + n) - a;
        ans.push_back({1, i});
        a[i] += k;
        clear();
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    normalize();

    for (int i = 0; i < k; ++i) {
        a[0] = a[n + 1] = i;
        for (int j = 0; j <= n; ++j) {
            diff[j] = (a[j] - a[j + 1] + k) % k;
        }

        for (int j = 0; j + k <= n; ++j) {
            diff[j + k] = (diff[j + k] + diff[j]) % k;
        }

        if (*max_element(diff + n - k + 1, diff + n + 1) == 0) {
            for (int j = 0; j + k <= n; ++j) {
                for (int l = 0; l < diff[j]; ++l) {
                    ans.push_back({2, j + 1});
                }

                for (int l = 1; l <= n; ++l) {
                    if (l <= j || l > j + k) {
                        ans.push_back({1, l});
                        ans.push_back({1, l});
                        a[l] += 2 * k - diff[j];
                    }
                }

                normalize();
            }

            cout << ans.size() << "\n";
            for (auto [t, x] : ans) {
                cout << t << " " << x << "\n";
            }
            exit(0);
        }
    }

    cout << -1 << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...