Submission #553331

#	Time	Username	Problem	Language	Result	Execution time	Memory
553331		RaresFelix	JOIRIS (JOI16_joiris)	C++17	15 / 100	1086 ms	596 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];
    for(int i = 1; i <= n; ++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 mi, ma;
        if(flag) {
            for(int i = 1; i <= n; ++i)
                V[i] -= V[n];
            for(int i = 1; i <= n; ++i)
                if(V[i] < 0) Sol.push_back({1, i}), V[i] += k;
        }
        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;
        mi = ma;
        for(int i = 1; i <= n; ++i)
            mi = min(mi, V[i]);
        for(int i = 1; i <= n; ++i) V[i] -= mi;
    };
    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);
        }
    };
    for(int i = 1; i <= n; ++i) R[(i - 1) % k] = (R[(i - 1) % k] + V[i]) % k;
    if(n % k) {
        int delta = R[0] - R[k - 1];
        delta = (delta % k + k) % k;
        for(int i = 1; i <= delta; ++i) swap_one();
    }
    int nr = 0;
    while(!solved()) {
        clean();
        ++nr;
    }
    cout << Sol.size() << "\n";
    for(auto [a, b] : Sol) cout << a << " " << b << "\n";
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 55