Submission #306462

#TimeUsernameProblemLanguageResultExecution timeMemory
306462jungsnowJOIRIS (JOI16_joiris)C++14
15 / 100
1 ms384 KiB
#include<bits/stdc++.h> #define x first #define y second #define bug(x) cerr<<#x<<" = "<<x<<'\n' using namespace std; typedef pair <int, int> ii; const int N = 55; int n, k, a[N], b[N]; bool tab[5 * N][N]; vector <ii> ans; void ver(int x) { ans.push_back({1, x + 1}); for (int j = 1; j <= k; ++j) { tab[a[x] + j][x] = 1; } a[x] += k; return; } void hor(int x) { if (x < k - 1) return; ans.push_back({2, x - k + 2}); int base = 0; for (int i = 0; i < k; ++i) base = max(base, a[x - i]); base++; for (int i = 0; i < k; ++i) { a[x - i] = base; tab[base][x - i] = 1; } return; } bool del(int x) { for (int i = 0; i < n; ++i) if (tab[x][i] == 0) return 0; for (int i = 0; i < n; ++i) { for (int j = x; j <= a[i]; ++j) { tab[j][i] = tab[j + 1][i]; } bool has = 0; for (int j = a[i]; j >= 0; --j) { if (tab[j][i]) { has = 1; a[i] = j; break; } } if (!has) a[i] = 0; } return 1; } void check() { int ma = 0; for (int i = 0; i < n; ++i) ma = max(ma, a[i]); for (int i = 1; i <= ma; ++i) while (del(i)); } void show() { for (int i = 0; i < n; ++i) { cerr << a[i] << '\n'; for (int j = 1; j <= 7; ++j) { cerr << tab[j][i]; } cerr << '\n'; } cerr<<'\n'; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("cc.inp", "r", stdin); // freopen("cc.out", "w", stdout); cin >> n >> k; for (int i = 0; i < n; ++i) { cin >> a[i]; for (int j = 1; j <= a[i]; j++) tab[j][i] = 1; b[i % k] += a[i]; b[i % k] %= k; } int m = n % k; // for (int i = 0; i < k; ++i) // bug(b[i]); if (0 <= m - 1) { for (int i = 1; i < k; ++i) if (i != m) { if (b[i] != b[i - 1]) { cout << -1; return 0; } } } check(); ///step - 1 for (int i = 1; i < n; ++i) while (a[i] < a[i - 1]) ver(i); check(); ///step - 2 for (int i = 1; i <= a[n - 1]; ++i) { int r = 0; for (r = 0; r < n; ++r) if (a[r] >= i) break; --r; while (r >= k - 1) { hor(r); r -= k; } } check(); ///step - 3 for (int i = 0; i < k - 1; ++i) { int ma = 0; for (int j = i; j < n; ++j) ma = max(ma, a[j]); while (a[i] < ma) ver(i); check(); } ///step - 4 int base = 0; for (int i = m; i < k - 1; ++i) base = max(base, a[i]); for (int i = m; i < k - 1; ++i) while (a[i] < base) ver(i); for (int i = 0; i < m; ++i) while (a[i] < base) ver(i); check(); ///step - 5 base = 0; for (int i = 0; i < m; ++i) base = max(base, a[i]); for (int i = 0; i < m; ++i) while (a[i] < base) ver(i); for (int i = 0; i < base; ++i) { for (int j = m; j < n; j += k) hor(j + k - 1); } ///cout cout << (int)ans.size() << '\n'; for (ii e : ans) { cout << e.x << ' ' << e.y << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...