oj.uz

Submission #311963

# Submission time Handle Problem Language Result Execution time Memory
311963 2020-10-12T04:49:53 Z limabeans JOIRIS (JOI16_joiris) C++17
30 / 100
 1 ms 512 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;


int n, k;
int a[maxn];
int b[maxn]; //sum(ith column) mod k

vector<pair<int,int>> ans;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>k;
    for (int i=0; i<n; i++) {
	cin>>a[i];
    }
    
    for (int i=0; i<n; i++) {
	b[i%k] += a[i];
	b[i%k] %= k;
    }

    for (int i=0; i<k; i++) {
	if (b[i] != b[0]) {
	    out(-1);
	}
    }



    // make a[i-1] <= a[i]
    for (int i=1; i<n; i++) {
	while (a[i-1]>a[i]) {
	    ans.push_back({1, i});
	    a[i] += k;
	}
    }


    
    for (int i=k-1; i<n-1; i++) {
	int dy = a[i+1]-a[i];
	int left = n;
	for (int y=0; y<dy; y++) {
	    for (int j=i-k+1; j>=0; j-=k) {
		left = min(left, j);
		ans.push_back({2, j});
	    }
	}
	for (int j=i; j>=left; j--) {
	    a[j] += dy;
	}
    }


    
    for (int i=0; i<k-1; i++) {
	while (a[i]<a[n-1]) {
	    ans.push_back({1, i});
	    a[i] += k;
	}
	assert(a[i]==a[0]);
    }


    int dy = a[0]-a[n-1];
    for (int y=0; y<dy; y++) {
	for (int i=k-1; i<n; i+=k) {
	    ans.push_back({2, i});
	}
    }



    cout<<ans.size()<<"\n";
    for (auto p: ans) {
	cout<<p.first<<" "<<1+p.second<<"\n";
    }
    
    
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 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 0 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 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct

Subtask #2
0 / 15.0

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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 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 0 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 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 0 ms 384 KB Output is correct
29 Correct 1 ms 512 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 0 ms 384 KB Output is correct
32 Correct 0 ms 384 KB Output is correct
33 Correct 0 ms 384 KB Output is correct
34 Correct 1 ms 384 KB Output is correct
35 Correct 0 ms 384 KB Output is correct
36 Correct 1 ms 384 KB Output is correct
37 Correct 0 ms 384 KB Output is correct
38 Correct 1 ms 384 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 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 0 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 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Incorrect 1 ms 384 KB Output isn't correct
18 Halted 0 ms 0 KB -