Submission #553327

#	Time	Username	Problem	Language	Result	Execution time	Memory
553327		RaresFelix	JOIRIS (JOI16_joiris)	C++17	30 / 100	4 ms	580 KiB

joiris

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