Submission #250702

#	Time	Username	Problem	Language	Result	Execution time	Memory
250702		ffao	JOIRIS (JOI16_joiris)	C++14	100 / 100	2 ms	392 KiB

joiris

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, k;
    cin >> n >> k;
    vi a(n); for (int i = 0; i < n; i++) cin >> a[i];
    vi oa = a;

    for (int tgt = 0; tgt < k; tgt++) {
        vector< pii > ops;
        a = oa;
        
        vi ms(n); for (int i = 0; i < n; i++) ms[i] = a[i] % k;

        for (int i = 0; i+k <= n; i++) {
            int mx = 0;
            for (int j = 0; j < k; j++) mx = max(mx, a[i+j]);

            while (ms[i] != tgt) {
                ops.push_back({2, i+1});
                for (int j = i; j < i+k; j++) {
                    ms[j]++; 
                    if (ms[j] >= k) ms[j]-=k;
                }

                for (int j = 0; j < n; j++) if (j < i || j >= i+k) {
                    while (a[j] < mx+1) {
                        ops.push_back({1,j+1});
                        a[j] += k;
                    }
                    a[j]--;
                }
            }
        }

        int mx = 0; bool ok = true;
        for (int i = 0; i < n; i++) {
            mx = max(mx, a[i]);
            if (ms[i] != tgt) ok = false;
        }

        if (!ok) continue;
        for (int i = 0; i < n; i++) {
            while (a[i] != mx) {
                ops.push_back({1,i+1}); a[i] += k;
            }
        }  

        cout << ops.size() << '\n';
        for (pii p : ops) {
            cout << p.first << " " << p.second << '\n';
        }
        return 0;
    }
    
    cout << -1 << endl;
}

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