#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], cntRMQ[N][20], logy[N], totalRemovals[N];
vector<ii> v;
vector<int> app[N], samePair[N];
int getMax(int l, int r) {
if (l > r) return 0;
int tmp = logy[r - l + 1];
return max(cntRMQ[l][tmp], cntRMQ[r - (1 << tmp) + 1][tmp]);
}
signed main() {
#ifdef BLU
in("blu.inp");
#endif
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m;
fw (i, 0, n) cin >> c[i];
if (m == 1) {
cout << "0";
return 0;
}
//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]]++;
//RMQ initialization
fw (i, 0, N) logy[i] = log2(i);
fw (i, 1, m + 1) cntRMQ[i][0] = cnt[i];
// fw (i, 1, m + 1) cout << cnt[i] << " "; cout << "\n";
fw (j, 1, 20) fw (i, 1, m + 1) if (i + (1 << (j - 1)) < n) {
cntRMQ[i][j] = max(cntRMQ[i][j - 1], cntRMQ[i + (1 << (j - 1))][j - 1]);
}
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(), samePair[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 (color, 1, m + 1) {
samePair[color].reserve(1 + app[color].size());
samePair[color].pb(color);
fa (pairID, app[color]) {
//Add color to other color's samePair vector.
if (v[pairID].fi != color) samePair[v[pairID].fi].pb(color);
if (v[pairID].se != color) samePair[v[pairID].se].pb(color);
}
}
fw (color, 1, m + 1) {
// samePair[color].resize(unique(samePair[color].begin(), samePair[color].end()) - samePair[color].begin());
int totalCost = 0, cntExcluded = 0;
//Find element with max cnt excluding all the pairs that color j appears in
if (i == 1 && c[0] == color) {
totalRemovals[c[0]]++;
cntExcluded++;
}
if (lastExcluded && c[n - 1] == color) {
totalRemovals[c[n - 1]]++;
cntExcluded++;
}
fa (pairID, app[color]) {
int cost = 0;
if (v[pairID].fi != color || v[pairID].se != color) cost = 1;
totalCost += cost;
totalRemovals[v[pairID].fi]++;
totalRemovals[v[pairID].se]++;
cntExcluded += 2;
}
//Calculating number that appears the most
int mxAppearances = 0;
fw (j, 0, samePair[color].size() + 1) {
if (j < samePair[color].size()) {
int curColor = samePair[color][j];
// cout << "curColor = " << curColor << " totalRemovals = " << totalRemovals[curColor] << "\n";
mxAppearances = max(mxAppearances, cnt[curColor] - totalRemovals[curColor]);
totalRemovals[curColor] = 0; //Reset total removals.
}
int prvColor = j ? samePair[color][j - 1] : 0;
int curColor = j < samePair[color].size() ? samePair[color][j] : m + 1;
prvColor++;
curColor--;
mxAppearances = max(mxAppearances, getMax(prvColor, curColor));
}
//cntIncluded counts the number of cords included in group 2.
int cntIncluded = n - cntExcluded;
totalCost += cntIncluded - mxAppearances;
// cout << "mxApperances = " << mxAppearances << " cntIncluded = " << cntIncluded << "\n";
ans[color] = min(ans[color], totalCost);
// cout << "i = " << i << " ans[" << color << "] = " << totalCost << "\n";
}
}
fw (color, 1, m + 1) cout << ans[color] << "\n";
return 0;
}
Compilation message
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:60:7:
fw (j, 0, v.size()) {
~~~~~~~~~~~~~~
rope.cpp:60:3: note: in expansion of macro 'fw'
fw (j, 0, v.size()) {
^~
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:97:8:
fw (j, 0, samePair[color].size() + 1) {
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
rope.cpp:97:4: note: in expansion of macro 'fw'
fw (j, 0, samePair[color].size() + 1) {
^~
rope.cpp:98:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (j < samePair[color].size()) {
~~^~~~~~~~~~~~~~~~~~~~~~~~
rope.cpp:105:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
int curColor = j < samePair[color].size() ? samePair[color][j] : m + 1;
~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
59044 KB |
Output is correct |
| 2 |
Correct |
70 ms |
59000 KB |
Output is correct |
| 3 |
Incorrect |
69 ms |
59052 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
59044 KB |
Output is correct |
| 2 |
Correct |
70 ms |
59000 KB |
Output is correct |
| 3 |
Incorrect |
69 ms |
59052 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
59044 KB |
Output is correct |
| 2 |
Correct |
70 ms |
59000 KB |
Output is correct |
| 3 |
Incorrect |
69 ms |
59052 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
59044 KB |
Output is correct |
| 2 |
Correct |
70 ms |
59000 KB |
Output is correct |
| 3 |
Incorrect |
69 ms |
59052 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
59044 KB |
Output is correct |
| 2 |
Correct |
70 ms |
59000 KB |
Output is correct |
| 3 |
Incorrect |
69 ms |
59052 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
