Submission #344317

#TimeUsernameProblemLanguageResultExecution timeMemory
344317MilladJOIRIS (JOI16_joiris)C++14
15 / 100
1089 ms492 KiB
// In the name of god #include <bits/stdc++.h> using namespace std; const int N = 105, MsK = 2e4, mod = 1e9 + 7; int n, k, a[N], b[N]; bool mrk[1255][55], mrk2[1255][55]; vector <pair<int, int>> vec; bool f(int i){ for(int j = 0; j < n; j ++)if(!mrk2[i][j])return 0; return 1; } void update(){ for(int i = 0; i <= 1254; i ++){ for(int j = 0; j < n; j ++)mrk2[i][j] = mrk[i][j]; } int I = 1254; for(int i = 1254; i >= 0; i --){ if(f(i))continue; for(int j = 0; j < n; j ++)mrk[I][j] = mrk2[i][j]; I --; } while(I >= 0){ for(int j = 0; j < n; j ++)mrk[I][j] = 0; I --; } } bool f2(){ for(int i = (n % k); i < k - 1; i ++)if(mrk[1254][i])return 1; return 0; } bool f3(){ for(int i = 0; i < (n % k); i ++)if(mrk[1254][i])return 1; return 0; } int main(){ ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> n >> k; for(int i = 0; i < n; i ++){ cin >> a[i]; b[i % k] = (b[i % k] + a[i]) % k; if(i > 0){ while(a[i] < a[i - 1]){ vec.push_back({1, i + 1}); a[i] += k; } } } int z = ((n % k) - 1 + k) % k; for(int i = 1; i <= z; i ++){ if(b[i] != b[i - 1])return cout << -1 << endl, 0; } z = (n % k); for(int i = z + 1; i < k; i ++){ if(b[i] != b[i - 1])return cout << -1 << endl, 0; } for(int i = n - 1; i >= 0; i --)a[i] -= a[0]; int Y = 1254; for(int i = 1; i < n; i ++){ for(int j = 0; j < a[i]; j ++)mrk[Y - j][i] = 1; } for(int i = Y; i > Y - a[n - 1]; i --){ for(int j = n - 1; j > k - 2; j --){ if(!mrk[i][j]){ vec.push_back({2, j - k + 2}); for(int h = j; h > j - k; h --)mrk[i][h] = 1; j -= k - 1; } } } update(); bool bl = 0; while(mrk[Y][n - 1]){ a[n - 1] = 0; int y = Y; while(mrk[y][n - 1]){ y --; a[n - 1] ++; } for(int i = 0; i < k - 1; i ++){ if(!bl){ a[i] = Y + 1; for(int j = 0; j <= Y; j ++){ if(mrk[j][i]){ a[i] = j; break; } } } while(a[i] > Y - a[n - 1] + 1){ vec.push_back({1, i + 1}); for(int h = a[i] - 1; h >= a[i] - k; h --)mrk[h][i] = 1; a[i] -= k; } } update(); bl = 1; } while((n % k) < k - 1 && f2()){ int mx = 0; for(int i = (n % k); i < k - 1; i ++){ int y = Y; a[i] = 0; while(mrk[y][i]){ a[i] ++; y --; } mx = max(mx, a[i]); } for(int i = 0; i < n; i ++){ int y = Y; a[i] = 0; while(mrk[y][i]){ a[i] ++; y --; } while(a[i] < mx){ for(int j = Y - a[i]; j > Y - a[i] - k; j --)mrk[j][i] = 1; a[i] += k; vec.push_back({1, i + 1}); } } update(); } bl = 0; while((n % k) - 1 >= 0 && f3()){ int mx = 0; int mn = 2000; for(int i = 0; i < (n % k); i ++){ if(!bl){ int y = Y; a[i] = 0; while(mrk[y][i]){ a[i] ++; y --; } } mn = min(mn, a[i]); mx = max(mx, a[i]); } for(int i = 0; i < (n % k); i ++)a[i] -= mn; mx -= mn; for(int i = 0; i < (n % k); i ++){ while(a[i] < mx){ a[i] += k; vec.push_back({1, i + 1}); } } int x = (n % k); mx += mn; while(x < n){ for(int j = Y; j > Y - mx; j --)vec.push_back({2, x + 1}); x += k; } bl = 1; } cout << vec.size() << "\n"; for(pair<int, int> i : vec)cout << i.first << ' ' << i.second << "\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...