Submission #289855

#	Time	Username	Problem	Language	Result	Execution time	Memory
289855		Diuven	JOIRIS (JOI16_joiris)	C++17	100 / 100	1 ms	384 KiB

joiris

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pii;

inline lint _min(lint x, lint y){ return x<y ? x : y; }
inline lint _max(lint x, lint y){ return x>y ? x : y; }
inline lint _abs(lint x){ return x<0 ? -x : x; }

int n, k, A[64];
vector<pii> ans;

void clear(int l, int r){
    for(int i=l; i<=r; i++) A[i]--;
}
void up(int i){
    A[i]+=k; ans.push_back({1, i});
}
void debug(){
    return;
    cout<<"Debug:\n";
    for(int i=1; i<=n; i++) cout<<A[i]<<' ';
    cout<<"\n\n";
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int C[64] = {};

	cin>>n>>k;
	for(int i=1; i<=n; i++) cin>>A[i], C[(i-1)%k]+=A[i];

	for(int i=0; i<n%k; i++) if(C[i]%k != C[0]%k){
	    cout<<"-1\n"; return 0;
    }
    for(int i=n%k; i<k; i++) if(C[i]%k != C[k-1]%k){
        cout<<"-1\n"; return 0;
    }

    for(int i=2; i<=n; i++){
        while(A[i]<A[i-1]) up(i);
    }
    debug();
    while(A[1]) clear(1, n);

    debug();

    for(int i=k+1; i<=n; i++){
        for(int b=A[i-1]; b<A[i]; b++){
            for(int a=(i-1)%k+1; a<i; a+=k){
                for(int j=a; j<a+k; j++) A[j]++;
                ans.push_back({2, a});
            }
        }
    }
    for(int i=1; i<k; i++){
        while(A[i]<A[n]) up(i);
    }
    while(A[n]) clear(1, n);

    debug();
    assert(A[k]==0);

    int mx = *max_element(A+n%k+1, A+k+1);
    for(int i=1; i<=n; i++){
        while(A[i]<mx) up(i);
    }
    while(A[k]) clear(1,n);

    debug();

    mx = *max_element(A+1, A+n%k+1);
    for(int i=1; i<=n%k; i++){
        while(A[i]<mx) up(i);
    }
    for(int i=n%k+1; i<=n; i+=k){
        while(A[i]<mx){
            for(int j=i; j<i+k; j++) A[j]++;
            ans.push_back({2, i});
        }
    }
    while(A[1]) clear(1, n);

    debug();

    cout<<ans.size()<<'\n';
    for(auto [a, b]: ans){
        cout<<a<<' '<<b<<'\n';
    }

	return 0;
}

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