oj.uz

Submission #289839

# Submission time Handle Problem Language Result Execution time Memory
289839 2020-09-03T06:35:06 Z Diuven JOIRIS (JOI16_joiris) C++17
0 / 100
 1 ms 384 KB 
#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);
    }
    while(A[1]) clear(1, n);

    debug();

    for(int i=1; i<=k; i++){
        for(int j=i+k; j<=n; j+=k){
            int x = A[j]-A[j-1];
            for(int b=0; b<x; b++){
                for(int a=i; a<j; a+=k){
                    ans.push_back({2, a});
                }
                clear(j, n); clear(1, i-1);
            }
        }
        debug();
        while(A[i]<A[n]) up(i);
        while(A[i+1]) 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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Incorrect 1 ms 384 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Incorrect 1 ms 384 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Incorrect 1 ms 384 KB Output isn't correct
12 Halted 0 ms 0 KB -