Submission #141095

#	Time	Username	Problem	Language	Result	Execution time	Memory
141095		DrumpfTheGodEmperor	Rope (JOI17_rope)	C++14	80 / 100	2548 ms	121780 KiB

rope

#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));
	}
}
ii getSecondMax() {
	set<ii>::iterator tmp = s.end();
	tmp--; tmp--;
	return *tmp;
}
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]);
	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]]++;
	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) {
//			Optimization: Don't remove color j from the set.
			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;
				
				if (v[pairID].fi != j) removeColor(v[pairID].fi);
				if (v[pairID].se != j) removeColor(v[pairID].se);
				
				cntExcluded += 2;
			}
			ii mostFrequentColor = *s.rbegin();
			if (mostFrequentColor.se == j) mostFrequentColor = getSecondMax();
			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:82:7:
   fw (j, 0, v.size()) {
       ~~~~~~~~~~~~~~                   
rope.cpp:82:3: note: in expansion of macro 'fw'
   fw (j, 0, v.size()) {
   ^~

• Subtask 1: 15 / 15
• Subtask 2: 30 / 30
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 0 / 20