Submission #397575

#TimeUsernameProblemLanguageResultExecution timeMemory
397575timmyfengRope (JOI17_rope)C++17
55 / 100
2586 ms96152 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1000001; int color[N], tally[N], ans[N]; map<int, int> pairs[N]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; for (int i = 0; i < n; ++i) { cin >> color[i]; ++tally[color[i]]; } multiset<int> maxi = {0}; for (int i = 1; i <= m; ++i) { maxi.insert(tally[i]); ans[i] = INT_MAX; } for (int k = 0; k < 2; ++k) { fill(pairs, pairs + m + 1, map<int, int>()); for (int i = k; i + 2 <= n; i += 2) { if (color[i] != color[i + 1]) { ++pairs[color[i]][color[i + 1]]; ++pairs[color[i + 1]][color[i]]; } } for (int i = 1; i <= m; ++i) { assert(maxi.find(tally[i]) != maxi.end()); maxi.erase(maxi.find(tally[i])); for (auto [j, k] : pairs[i]) { assert(maxi.find(tally[j]) != maxi.end()); maxi.erase(maxi.find(tally[j])); maxi.insert(tally[j] - k); } assert(!maxi.empty()); ans[i] = min(ans[i], n - tally[i] - *(--maxi.end())); for (auto [j, k] : pairs[i]) { assert(maxi.find(tally[j] - k) != maxi.end()); maxi.erase(maxi.find(tally[j] - k)); maxi.insert(tally[j]); } maxi.insert(tally[i]); } } for (int i = 1; i <= m; ++i) { cout << ans[i] << "\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...
#Verdict Execution timeMemoryGrader output
Fetching results...