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>
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s, "r", stdin);
#define out(s) freopen(s, "w", stdout);
#define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\
freopen((string(s) + "." + end2).c_str(), "w", stdout);
#define fi first
#define se second
#define bw(i, r, l) for (int i = r - 1; i >= l; i--)
#define fw(i, l, r) for (int i = l; i < r; i++)
#define fa(i, x) for (auto i: x)
using namespace std;
typedef pair<int, int> ii;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4557430888798830399;
const int N = 1e6 + 5;
int n, m, c[N], ans[N], cnt[N], curCnt[N];
vector<ii> v;
vector<int> app[N];
set<ii> s;
void read(int &number) {
bool negative = false; register int c;
number = 0; c = getchar();
while (c != '-' && (c <= 47 || c >= 58)) c = getchar();
if (c == '-') {
negative = 1;
c = getchar();
}
while (c > 47 && c < 58) {
number = (number << 3) + (number << 1) + c - 48;
c = getchar();
}
if (negative) number = -number;
}
void removeColor(int color) {
s.erase(s.lower_bound(ii(curCnt[color], color)));
// cout << "Remove " << color << "\n";
curCnt[color]--;
s.insert(ii(curCnt[color], color));
}
void resetColor(int color) {
if (curCnt[color] != cnt[color]) {
s.erase(s.lower_bound(ii(curCnt[color], color)));
curCnt[color] = cnt[color];
s.insert(ii(curCnt[color], color));
}
}
signed main() {
#ifdef BLU
in("blu.inp");
#endif
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
read(n), read(m);
fw (i, 0, n) read(c[i]);
//Pre - color the rope then fold. Folding can be done if segments of the same color, except the first
//and last one are all of even length.
memset(ans, 63, sizeof ans);
memset(cnt, 0, sizeof cnt);
fw (i, 0, n) cnt[c[i]]++;
fw (i, 1, m + 1) s.insert(ii(cnt[i], i)), curCnt[i] = cnt[i];
fw (i, 0, 2) {
bool lastExcluded = 0;
if (i == 0 && (n & 1)) lastExcluded = 1;
if (i == 1 && !(n & 1)) lastExcluded = 1;
//Fix the first segment one as either odd or even.
fw (color, 1, m + 1) app[color].clear();
v.clear();
for (int j = i; j < n; j += 2) {
if (j + 1 >= n) break;
v.pb(ii(c[j], c[j + 1]));
}
fw (j, 0, v.size()) {
app[v[j].fi].pb(j);
if (v[j].se != v[j].fi) app[v[j].se].pb(j);
}
fw (j, 1, m + 1) {
int totalCost = 0, cntExcluded = 0;
//Find element with max cnt excluding all the pairs that color j appears in
if (i == 1 && c[0] == j) {
removeColor(c[0]);
cntExcluded++;
}
if (lastExcluded && c[n - 1] == j) {
removeColor(c[n - 1]);
cntExcluded++;
}
fa (pairID, app[j]) {
int cost = 0;
if (v[pairID].fi != j || v[pairID].se != j) cost = 1;
totalCost += cost;
removeColor(v[pairID].fi);
removeColor(v[pairID].se);
cntExcluded += 2;
}
ii mostFrequentColor = *s.rbegin();
int mxAppearances = mostFrequentColor.fi, cntIncluded = n - cntExcluded;
//cntIncluded counts the number of cords included in group 2.
totalCost += cntIncluded - mxAppearances;
// cout << "the pair is: " << mostFrequentColor.fi << " " << mostFrequentColor.se << "\n";
// cout << "mxApperances = " << mxAppearances << " cntIncluded = " << cntIncluded << "\n";
ans[j] = min(ans[j], totalCost);
// cout << "i = " << i << " ans[" << j << "] = " << totalCost << "\n";
//Reset curCnt and the set.
fa (pairID, app[j]) {
resetColor(v[pairID].fi);
resetColor(v[pairID].se);
}
resetColor(c[0]);
resetColor(c[n - 1]);
}
}
fw (color, 1, m + 1) cout << ans[color] << "\n";
return 0;
}
Compilation message (stderr)
rope.cpp: In function 'int main()':
rope.cpp:11:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define fw(i, l, r) for (int i = l; i < r; i++)
rope.cpp:73:7:
fw (j, 0, v.size()) {
~~~~~~~~~~~~~~
rope.cpp:73:3: note: in expansion of macro 'fw'
fw (j, 0, v.size()) {
^~
# | 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... |