Submission #328040

#	Time	Username	Problem	Language	Result	Execution time	Memory
328040		natsugirl	JOIRIS (JOI16_joiris)	C++17	100 / 100	1 ms	384 KiB

joiris

/**** 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 (stderr)

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 / 15
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 55 / 55