oj.uz

Submission #328040

# Submission time Handle Problem Language Result Execution time Memory
328040 2020-11-15T09:21:02 Z natsugirl JOIRIS (JOI16_joiris) C++17
100 / 100
 1 ms 384 KB 
/**** Hyperhydrochloric Acid ****\
|                H    H          |
|                 \  /           |
|             H    Cl            |
|              \  /              |
|   H           Cl               |
|    \          |                |
|     Cl        Cl        H      |
|    /  \      /  \      /       |
|   H    Cl--Cl    Cl--Cl    H   |
|       /      \  /      \  /    |
|      H        Cl        Cl     |
|               |           \    |
|               H            H   |
\********************************/
#include <bits/stdc++.h>
using namespace std;
#define SZ(x)               ((int)(x).size())
#define all(x)              (x).begin(), (x).end()
#define loop(i, n)          for(int i = 0; i < (n); ++i)
#define cont(i, n)          for(int i = 1; i <= (n); ++i)
#define circ(i, a, b)       for(int i = (a); i <= (b); ++i)
#define range(i, a, b, c)   for(int i = (a); ((c) > 0 ? i <= (b) : i >= (b)); i += (c))
#define foreach(it, v)      for(__typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it)
#define y0          y0O0OO00OO0OO0OO0OOO00OO0OO0O0O000OO0
#define y1          y1II11II11III11I1III11II111IIII1II1I1
#define pub         push_back
#define pob         pop_back
#define mak         make_pair
typedef long long   ll;
typedef long double lf;
const int   Inf = 0x3f3f3f3f;
const ll    INF = 0x3f3f3f3f3f3f3f3fll;
/* Source code starts here */

int n, k;
int a[55], S[55];
vector<pair<int, int> > op;

void inline debug() {
	int mxh = 0;
	loop(i, n) mxh = max(mxh, a[i]);
	range(i, mxh, 1, -1) {
		printf("%4d ", i);
		loop(j, n) {
			if(a[j] >= i) printf("#");
			else printf(" ");
		}
		puts("");
	}
	puts("");
}

int main() {
	scanf("%d%d", &n, &k);
	loop(i, n) scanf("%d", a + i);
	loop(i, n) (S[i % k] += a[i]) %= k;
	cont(i, n % k - 1) if(S[i] != S[i - 1]) return puts("-1"), 0;
	circ(i, n % k + 1, k - 1) if(S[i] != S[i - 1]) return puts("-1"), 0;
	// Oper 1
	range(i, n - 1, 0, -1) {
		while(a[i] < a[i + 1]) {
			a[i] += k; op.pub(mak(1, i));
		}
	}
	// Oper 2
	int hi = a[0];
	vector<int> wid;
	int ptr = n - 1;
	cont(i, hi) {
		while(a[ptr] < i) --ptr;
		if(ptr == n - 1) {
			loop(i, n) --a[i];
			--i; --hi; continue;
		}
		int np = ptr + 1;
		while(np + k <= n) {
			op.pub(mak(2, np));
			np += k;
		}
		wid.pub(np - 1);
	}
	// Oper 3
	loop(i, SZ(wid)) {
		if(wid[i] == n - 1) {
			wid.erase(wid.begin() + i);
			--i;
		}
	}
	range(i, n - 1, n - k + 1, -1) {
		int mxh = -1;
		loop(j, SZ(wid)) if(wid[j] == i - 1) mxh = j;
		while(a[i] < hi) {
			a[i] += k; op.pub(mak(1, i));
			mxh -= k;
		}
		int rm = 0;
		loop(j, SZ(wid)) {
			if(wid[j] == i - 1) {
				wid.erase(wid.begin() + j);
				--j; ++rm;
			}
		}
		a[i - 1] = 0;
		circ(j, i, n - 1) a[j] -= rm;
		hi -= rm;
		// cerr<<hi<<' '<<i<<endl;
		// debug();
	}
	// debug();
	loop(i, n - k + 1) a[i] = 0;
	// Oper 4
	int fk = n - k, fkm = n - n % k - 1;
	int mxh = 0;
	circ(i, fk, fkm) mxh = max(mxh, a[i]);
	circ(i, fkm + 1, n - 1) {
		while(a[i] < mxh) {
			a[i] += k; op.pub(mak(1, i));
		}
	}
	assert(mxh % k == 0);
	circ(i, fk, fkm) {
		while(a[i] < mxh) {
			a[i] += k; op.pub(mak(1, i));
		}
		assert(a[i] == mxh);
	}
	loop(i, fk) {
		a[i] = 0;
		while(a[i] < mxh) {
			a[i] += k; op.pub(mak(1, i));
		}
	}
	loop(i, n) a[i] -= mxh;
	// Oper 5
	mxh = 0;
	circ(i, fkm + 1, n - 1) mxh = max(mxh, a[i]);
	// cerr<<mxh<<endl;
	// debug();
	circ(i, fkm + 1, n - 1) {
		// cerr<<i<<' '<<a[i]<<endl;
		while(a[i] < mxh) {
			a[i] += k; op.pub(mak(1, i));
		}
		assert(a[i] == mxh);
	}
	loop(i, mxh) {
		range(j, 0, fkm, k) {
			op.pub(mak(2, j));
		}
	}
	// Output
	printf("%d\n", SZ(op));
	loop(i, SZ(op)) printf("%d %d\n", op[i].first, op[i].second + 1);
	return 0;
}

/**
 * 思考时间：9:30-10:30, 14:00-15:20, 2h20min
 * 实现时间：15:20-
 * 实现思路
 *  首先，有一个结论：有解当且仅当所有模 k 等于 i 的列（i < n % k，0 based）的高度之和（称为 Si）模 k 相等，且对于 n % k <= i < k 同样成立。
 *   必要性证明显然，每次操作（横、竖、删一行），这两部分中每部分的 Si 大小关系都不变。下面考虑证明充分性，并构造解法。
 *  从右往左不断加竖着的块，使得所有列的高度单调递减。
 *  对于每个高度，如果最后一个高于这个高度的列是 i，则从 i + 1 开始不断放横着的块，直到最后放不下为止，使得除了最后 k - 1 列以外所有列等高。
 *  从最后一列到倒数第 k - 1 列，不断放竖着的块，使得除了最后 k - 1 列以外的所有列全部清空。
 *  由于开头的结论，且倒数 k 列已被清空，所以倒数 k 列至倒数 n % k + 1 列的高度模 k 全为 0
 *   此时将倒数 k 列至倒数 n % k + 1 列用竖着的块填平，对前面的列不断放竖着的块，直到只有最后 n % k 列非空为止。
 *  最后，用竖着的块将最后 n % k 列填平，对前面的列不断放横着的块，直到所有块都被消除。
 *  前三个操作、第四个操作、第五个操作各最多只会填满 nk 层，故最多只会各用 n^2 个块，所以不会超过 10000 的限制。
 */

Compilation message

joiris.cpp: In function 'int main()':
joiris.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
joiris.cpp:56:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |  loop(i, n) scanf("%d", a + i);
      |             ~~~~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 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 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 0 ms 364 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 364 KB Output is correct

Subtask #3
15.0 / 15.0

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

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 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 1 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 0 ms 364 KB Output is correct
13 Correct 0 ms 364 KB Output is correct
14 Correct 0 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 0 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Correct 0 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 1 ms 364 KB Output is correct
32 Correct 1 ms 364 KB Output is correct
33 Correct 0 ms 364 KB Output is correct
34 Correct 1 ms 364 KB Output is correct
35 Correct 1 ms 364 KB Output is correct
36 Correct 1 ms 364 KB Output is correct
37 Correct 1 ms 364 KB Output is correct
38 Correct 1 ms 384 KB Output is correct
39 Correct 1 ms 364 KB Output is correct
40 Correct 1 ms 364 KB Output is correct
41 Correct 1 ms 364 KB Output is correct
42 Correct 1 ms 364 KB Output is correct
43 Correct 1 ms 364 KB Output is correct
44 Correct 1 ms 364 KB Output is correct
45 Correct 1 ms 364 KB Output is correct
46 Correct 1 ms 364 KB Output is correct
47 Correct 1 ms 364 KB Output is correct
48 Correct 1 ms 364 KB Output is correct
49 Correct 1 ms 364 KB Output is correct
50 Correct 1 ms 364 KB Output is correct
51 Correct 1 ms 364 KB Output is correct
52 Correct 1 ms 364 KB Output is correct
53 Correct 1 ms 364 KB Output is correct
54 Correct 1 ms 364 KB Output is correct
55 Correct 1 ms 364 KB Output is correct
56 Correct 1 ms 364 KB Output is correct
57 Correct 1 ms 364 KB Output is correct
58 Correct 1 ms 364 KB Output is correct
59 Correct 1 ms 364 KB Output is correct
60 Correct 1 ms 364 KB Output is correct
61 Correct 1 ms 364 KB Output is correct
62 Correct 1 ms 364 KB Output is correct
63 Correct 1 ms 364 KB Output is correct
64 Correct 1 ms 364 KB Output is correct
65 Correct 1 ms 364 KB Output is correct
66 Correct 1 ms 364 KB Output is correct
67 Correct 1 ms 364 KB Output is correct
68 Correct 1 ms 364 KB Output is correct
69 Correct 1 ms 364 KB Output is correct
70 Correct 1 ms 364 KB Output is correct
71 Correct 1 ms 364 KB Output is correct
72 Correct 1 ms 364 KB Output is correct
73 Correct 1 ms 364 KB Output is correct
74 Correct 1 ms 364 KB Output is correct
75 Correct 1 ms 364 KB Output is correct
76 Correct 1 ms 364 KB Output is correct
77 Correct 1 ms 364 KB Output is correct
78 Correct 1 ms 364 KB Output is correct
79 Correct 1 ms 364 KB Output is correct
80 Correct 0 ms 364 KB Output is correct
81 Correct 1 ms 364 KB Output is correct
82 Correct 1 ms 364 KB Output is correct
83 Correct 1 ms 364 KB Output is correct
84 Correct 1 ms 364 KB Output is correct
85 Correct 1 ms 364 KB Output is correct
86 Correct 1 ms 364 KB Output is correct
87 Correct 1 ms 364 KB Output is correct
88 Correct 1 ms 384 KB Output is correct
89 Correct 1 ms 364 KB Output is correct
90 Correct 1 ms 364 KB Output is correct
91 Correct 1 ms 364 KB Output is correct
92 Correct 1 ms 364 KB Output is correct