oj.uz

Submission #344164

# Submission time Handle Problem Language Result Execution time Memory
344164 2021-01-05T08:04:50 Z Millad JOIRIS (JOI16_joiris) C++14
30 / 100
 1000 ms 512 KB 
// In the name of god
#include <bits/stdc++.h>
using namespace std;
const int N = 105, MsK = 2e4, mod = 1e9 + 7;
int n, k, a[N], b[N];
bool mrk[1305][55], mrk2[1305][55];
vector <pair<int, int>> vec;
bool f(int i){
	for(int j = 0; j < n; j ++)if(!mrk2[i][j])return 0;
	return 1;
}
void update(){
	for(int i = 0; i <= 1304; i ++){
		for(int j = 0; j < n; j ++)mrk2[i][j] = mrk[i][j];
	}
	int I = 1304;
	for(int i = 1304; i >= 0; i --){
		if(f(i))continue;
		for(int j = 0; j < n; j ++)mrk[I][j] = mrk2[i][j];
		I --;
	}
	while(I >= 0){
		for(int j = 0; j < n; j ++)mrk[I][j] = 0;
		I --;
	}
}
bool f2(){
	for(int i = (n % k); i < k - 1; i ++)if(mrk[1304][i])return 1;
	return 0;
}
bool f3(){
	for(int i = 0; i < (n % k); i ++)if(mrk[1304][i])return 1;
	return 0;
}
int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> k;
	for(int i = 0; i < n; i ++){
		cin >> a[i];
		b[i % k] = (b[i % k] + a[i]) % k;
		if(i > 0){
			while(a[i] < a[i - 1]){
				vec.push_back({1, i + 1});
				a[i] += k;
			}
		}
	}
	int z = ((n % k) - 1 + k) % k;
	for(int i = 1; i <= z; i ++){
		if(b[i] != b[i - 1])return cout << -1 << endl, 0;
	}
	z = (n % k);
	for(int i = z + 1; i < k; i ++){
		if(b[i] != b[i - 1])return cout << -1 << endl, 0;
	}
	for(int i = n - 1; i >= 0; i --)a[i] -= a[0];
	int Y = 1304;
	for(int i = 1; i < n; i ++){
		for(int j = 0; j < a[i]; j ++)mrk[Y - j][i] = 1;
	}
	for(int i = Y; i > Y - a[n - 1]; i --){
		for(int j = n - 1; j > k - 2; j --){
			if(!mrk[i][j]){
				vec.push_back({2, j - k + 2});
				for(int h = j; h > j - k; h --)mrk[i][h] = 1;
				j -= k - 1;
			}
		}
	}
	update();
	while(mrk[Y][n - 1]){
		a[n - 1] = 0;
		int y = Y;
		while(mrk[y][n - 1]){
			y --;
			a[n - 1] ++;
		}
		for(int i = 0; i < k - 1; i ++){
			int yy = Y + 1;
			for(int j = 0; j <= Y; j ++){
				if(mrk[j][i]){
					yy = j;
					break;
				}
			}
			while(yy > Y - a[n - 1] + 1){
				vec.push_back({1, i + 1});
				for(int h = yy - 1; h >= yy - k; h --)mrk[h][i] = 1;
				yy -= k;
			}
		}
		update();
	}
	while((n % k) < k - 1 && f2()){
		int mx = 0;
		for(int i = (n % k); i < k - 1; i ++){
			int y = Y;
			a[i] = 0;
			while(mrk[y][i]){
				a[i] ++;
				y --;
			}
			mx = max(mx, a[i]);
		}
		for(int i = 0; i < n; i ++){
			while(a[i] < mx){
				for(int j = Y - a[i]; j > Y - a[i] - k; j --)mrk[j][i] = 1;
				a[i] += k;
				vec.push_back({1, i + 1});
			}
		}
		update();
	}
	while((n % k) - 1 >= 0 && f3()){
		int mx = 0;
		for(int i = 0; i < (n % k); i ++){
			int y = Y;
			a[i] = 0;
			while(mrk[y][i]){
				a[i] ++;
				y --;
			}
			mx = max(mx, a[i]);
		}
		for(int i = 0; i < (n % k); i ++){
			while(a[i] < mx){
				a[i] += k;
				vec.push_back({1, i + 1});
			}
			for(int j = Y - (mx - a[i]); j > Y - mx; j --)mrk[j][i] = 0;
			for(int j = Y; j > Y - (mx - a[i]); j --)mrk[j][i] = 1;
		}
		int x = (n % k);
		while(x < n){
			for(int j = Y; j > Y - mx; j --)vec.push_back({2, x + 1});
			x += k;
		}
	}
	cout << vec.size() << "\n";
	for(auto i : vec)cout << i.first << ' ' << i.second << "\n";
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 492 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 512 KB Output is correct
16 Correct 1 ms 492 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 492 KB Output is correct
17 Correct 0 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Execution timed out 1084 ms 492 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 492 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 1 ms 492 KB Output is correct
19 Correct 1 ms 492 KB Output is correct
20 Correct 1 ms 492 KB Output is correct
21 Correct 1 ms 492 KB Output is correct
22 Correct 1 ms 492 KB Output is correct
23 Correct 1 ms 492 KB Output is correct
24 Correct 1 ms 492 KB Output is correct
25 Correct 1 ms 492 KB Output is correct
26 Correct 1 ms 492 KB Output is correct
27 Correct 1 ms 492 KB Output is correct
28 Correct 1 ms 492 KB Output is correct
29 Correct 1 ms 492 KB Output is correct
30 Correct 1 ms 492 KB Output is correct
31 Correct 1 ms 512 KB Output is correct
32 Correct 1 ms 492 KB Output is correct
33 Correct 0 ms 364 KB Output is correct
34 Correct 1 ms 364 KB Output is correct
35 Execution timed out 1084 ms 492 KB Time limit exceeded
36 Halted 0 ms 0 KB -