Submission #328040

#TimeUsernameProblemLanguageResultExecution timeMemory
328040natsugirlJOIRIS (JOI16_joiris)C++17
100 / 100
1 ms384 KiB
/**** 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);
      |             ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...