Submission #553385

#TimeUsernameProblemLanguageResultExecution timeMemory
553385RaresFelixJOIRIS (JOI16_joiris)C++17
100 / 100
1 ms340 KiB
#include <bits/stdc++.h> using namespace std; int main() { cin.tie(0)->sync_with_stdio(0); int n, k; cin >> n >> k; vector<int> V(n + 1), R(k); for(int i = 1; i <= n; ++i) cin >> V[i], R[(i - 1) % k] = (R[(i - 1) % k] + V[i]) % k; bool ok = true; for(int i = 0; i < n % k - 1; ++i) ok &= R[i] == R[i + 1]; for(int i = n % k; i < k - 1; ++i) ok &= R[i] == R[i + 1]; if(!ok) { cout << "-1\n"; return 0; } vector<int> Sol; for(int i = 2; i <= n; ++i) while(V[i] < V[i-1]) V[i] += k, Sol.push_back(i); int nrlin = 0; vector<int> S(n + 2); for(int i = k; i < n; ++i) { for(int rep = V[i + 1] - V[i]; rep --> 0;) for(int j = i; j >= k; j -= k) Sol.push_back(-(j - k + 1)), ++S[j - k + 1], --S[j + 1]; nrlin += V[i + 1] - V[i]; } for(int i = 1; i <= n; ++i) S[i] += S[i-1], V[i] += S[i]; for(int i = 1; i <= k; ++i) while(V[i] < V[n]) V[i] += k, Sol.push_back(i); int mi = numeric_limits<int>::max() / 4; for(int i = 1; i <= n; ++i) { mi = min(mi, V[i] -= nrlin); } for(int i = 1; i <= n; ++i) V[i] -= mi, S[i] = 0; for(int rep = 1; rep <= V[1]; ++rep) for(int i = n % k + 1; i <= n; i += k) Sol.push_back(-i), ++S[i], --S[i + k]; for(int i = 1; i <= n; ++i) S[i] += S[i-1], V[i] += S[i]; mi = numeric_limits<int>::max() / 4; ok = 1; for(int i = 1; i <= n; ++i) mi = min(mi, V[i]); for(int i = 1; i <= n; ++i) ok &= (V[i] == mi); if(!ok) { cout << "-1\n"; return 0; } cout << Sol.size() << "\n"; for(auto it : Sol) cout << (it > 0 ? "1 " : "2 ") << abs(it) << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...