Submission #1079154

#TimeUsernameProblemLanguageResultExecution timeMemory
1079154boris_mihovJOIRIS (JOI16_joiris)C++17
0 / 100
982 ms66176 KiB
#include <unordered_map> #include <algorithm> #include <iostream> #include <numeric> #include <cassert> #include <vector> #include <ctime> #include <map> typedef long long llong; const int MAXN = 100000 + 10; const int INF = 1e9; int n, k; int a[MAXN]; int cnt[MAXN]; std::vector <std::pair <char,short>> ops; double begTime; void solve() { while ((clock() - begTime) / CLOCKS_PER_SEC < 0.98) { int min = INF, max = 0; for (int i = 1 ; i <= n ; ++i) { min = std::min(min, a[i]); } for (int i = 1 ; i <= n ; ++i) { a[i] -= min; max = std::max(max, a[i]); } if (max == 0 || ops.size() > 1e7) { break; } for (int i = n ; i >= 1 ; --i) { if (a[i] > 0) { cnt[i] = 0; } else { cnt[i] = 1 + cnt[i + 1]; } } bool done = false; for (int i = 1 ; i <= n ; ++i) { if (cnt[i] >= k) { for (int j = i ; j < i + k ; ++j) { a[j]++; } ops.push_back({2, i}); done = true; break; } } if (done) { continue; } for (int i = 1 ; i <= n ; ++i) { if (a[i] == 0) { ops.push_back({1, i}); a[i] += k; } } } } void input() { std::cin >> n >> k; for (int i = 1 ; i <= n ; ++i) { std::cin >> a[i]; } } void print() { for (int i = 1 ; i <= n ; ++i) { if (a[i] > 0) { std::cout << -1 << '\n'; return; } } std::cout << ops.size() << '\n'; for (const auto &[x, y] : ops) { std::cout << (short)x << ' ' << y << '\n'; } } void fastIOI() { std::ios_base :: sync_with_stdio(0); std::cout.tie(nullptr); std::cin.tie(nullptr); } int main() { begTime = clock(); fastIOI(); input(); solve(); print(); 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...