oj.uz

Submission #322623

# Submission time Handle Problem Language Result Execution time Memory
322623 2020-11-15T03:30:53 Z Eric_hoo JOIRIS (JOI16_joiris) C++14
15 / 100
 3 ms 384 KB 
#include <bits/stdc++.h>
using namespace std;

int a[60], b[60], c[60];
int n, k;
vector <int> op;

bool alive() {
	for (int i = 0; i < n; i++) {
		if (a[i] >= k) return 0;
	}
	return 1;
}

void calc() {
	int minj = 0x3f3f3f3f;
	for (int i = 0; i < n; i++) {
		if (a[i] == 0) a[i] = k, op.push_back(i << 1);
		minj = min(minj, a[i]);
	}
	for (int i = 0; i < n; i++) {
		a[i] -= minj;
	}
}

int main () {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	if (k == n) {
		printf("-1\n");
		return 0;
	}
	while (!alive()) calc();
	for (int i = 0; i < n; i++) {
		b[i] = k - a[i] - 1;
	}
	int flag = 0;
	for (int B = 0; B < k; B++) {
		memset(c, 0, sizeof(c));
		for (int i = 0; i < n; i++) {
			b[i] = k - a[i] - 1;
		}
		for (int i = 0; i <= n - k; i++) {
			c[i] = (B - b[i] + k) % k;
			for (int j = i; j < i + k; j++) {
				b[j] = (b[j] + c[i]) % k;
			}
		}
		for (int i = 0; i < n; i++) {
			if (b[i] != B) goto END;
		}
		flag = 1;
		break;
		END:;
	}
	if (!flag) {
		cout << -1 << endl;
		return 0;
	}
	for (int i = 0; i <= n - k; i++) {
		if (!c[i]) continue;
		for (int j = 0; j < c[i]; j++) {
			op.push_back(i << 1 | 1);
		}
		int maxj = -1;
		for (int j = i; j < i + k; j++) {
			maxj = max(maxj, a[j]);
		}
		maxj += c[i];
		for (int j = 0; j < n; j++) {
			if (j >= i && j < i + k) continue;
			while (a[j] < maxj) a[j] += k, op.push_back(j << 1);
			a[j] -= c[i];
		}
		while (!alive()) calc();
	}
	cout << op.size() << endl;
	for (int i = 0; i < op.size(); i++) {
		int x = op[i];
		cout << (x & 1) + 1 << " " << (x >> 1) + 1 << endl;
	}
	return 0;
}

Compilation message

joiris.cpp: In function 'int main()':
joiris.cpp:80:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for (int i = 0; i < op.size(); i++) {
      |                  ~~^~~~~~~~~~~

Subtask #1
0 / 15.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 372 KB Output is correct
5 Correct 3 ms 364 KB Output is correct
6 Correct 3 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 2 ms 364 KB Output is correct
12 Correct 2 ms 364 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 2 ms 364 KB Output is correct
16 Correct 1 ms 364 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 1 ms 384 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 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 1 ms 384 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -