This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<int> c(n);
for (int i = 0; i < n; ++i) {
cin >> c[i];
--c[i];
}
vector<int> cnt(m, 0);
for (int i = 0; i < n; ++i) {
++cnt[c[i]];
}
vector<int> ans(m);
for (int u = 0; u < m; ++u) {
ans[u] = n - cnt[u];
}
for (int p = 0; p < 2; ++p) {
map<pair<int, int>, int> mp;
vector<vector<int>> g(m);
for (int i = p; i + 1 < n; i += 2) {
if (c[i] != c[i + 1]) {
++mp[{c[i], c[i + 1]}];
++mp[{c[i + 1], c[i]}];
g[c[i]].push_back(c[i + 1]);
g[c[i + 1]].push_back(c[i]);
}
}
set<pair<int, int>> s;
for (int u = 0; u < m; ++u) {
s.insert({cnt[u], u});
}
for (int u = 0; u < m; ++u) {
sort(begin(g[u]), end(g[u]));
g[u].resize(unique(begin(g[u]), end(g[u])) - begin(g[u]));
for (int v : g[u]) {
ans[u] = min(ans[u], n - cnt[u] - cnt[v] + mp[{u, v}]);
}
for (int v : g[u]) {
s.erase({cnt[v], v});
}
s.erase({cnt[u], u});
ans[u] = min(ans[u], n - cnt[u] - (s.empty() ? 0 : s.rbegin()->first));
s.insert({cnt[u], u});
for (int v : g[u]) {
s.insert({cnt[v], v});
}
}
}
for (int u = 0; u < m; ++u) {
cout << ans[u] << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |