Submission #141233

#	Time	Username	Problem	Language	Result	Execution time	Memory
141233		DrumpfTheGodEmperor	Rope (JOI17_rope)	C++14	100 / 100	2483 ms	225468 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], cntRMQ[N][20], logy[N], totalRemovals[N], appSize[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, 1, m + 1) app[j].reserve(cnt[j]);
		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";
					if (j == 0 || curColor != samePair[color][j - 1]) {
						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 (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:61:7:
   fw (j, 0, v.size()) {
       ~~~~~~~~~~~~~~                   
rope.cpp:61: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:98:8:
    fw (j, 0, samePair[color].size() + 1) {
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
rope.cpp:98:4: note: in expansion of macro 'fw'
    fw (j, 0, samePair[color].size() + 1) {
    ^~
rope.cpp:99:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (j < samePair[color].size()) {
         ~~^~~~~~~~~~~~~~~~~~~~~~~~
rope.cpp:108:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     int curColor = j < samePair[color].size() ? samePair[color][j] : m + 1;
                    ~~^~~~~~~~~~~~~~~~~~~~~~~~

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