oj.uz

Submission #141085

# Submission time Handle Problem Language Result Execution time Memory
141085 2019-08-06T15:58:04 Z DrumpfTheGodEmperor Rope (JOI17_rope) C++14
80 / 100
 2500 ms 121900 KB 
#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#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 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);
	cin >> n >> m;
	fw (i, 0, n) cin >> 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

rope.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
rope.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
rope.cpp: In function 'int main()':
rope.cpp:14: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:62:7:
   fw (j, 0, v.size()) {
       ~~~~~~~~~~~~~~                   
rope.cpp:62:3: note: in expansion of macro 'fw'
   fw (j, 0, v.size()) {
   ^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31608 KB Output is correct
2 Correct 31 ms 31608 KB Output is correct
3 Correct 31 ms 31608 KB Output is correct
4 Correct 31 ms 31732 KB Output is correct
5 Correct 30 ms 31620 KB Output is correct
6 Correct 31 ms 31608 KB Output is correct
7 Correct 30 ms 31736 KB Output is correct
8 Correct 31 ms 31736 KB Output is correct
9 Correct 30 ms 31736 KB Output is correct
10 Correct 37 ms 31736 KB Output is correct
11 Correct 30 ms 31736 KB Output is correct
12 Correct 31 ms 31608 KB Output is correct
13 Correct 30 ms 31736 KB Output is correct
14 Correct 31 ms 31612 KB Output is correct
15 Correct 30 ms 31736 KB Output is correct
16 Correct 37 ms 31736 KB Output is correct
17 Correct 31 ms 31736 KB Output is correct
18 Correct 31 ms 31720 KB Output is correct
19 Correct 31 ms 31736 KB Output is correct
20 Correct 31 ms 31608 KB Output is correct
21 Correct 30 ms 31608 KB Output is correct
22 Correct 31 ms 31736 KB Output is correct
23 Correct 30 ms 31736 KB Output is correct
24 Correct 31 ms 31608 KB Output is correct
25 Correct 31 ms 31736 KB Output is correct
26 Correct 31 ms 31736 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31608 KB Output is correct
2 Correct 31 ms 31608 KB Output is correct
3 Correct 31 ms 31608 KB Output is correct
4 Correct 31 ms 31732 KB Output is correct
5 Correct 30 ms 31620 KB Output is correct
6 Correct 31 ms 31608 KB Output is correct
7 Correct 30 ms 31736 KB Output is correct
8 Correct 31 ms 31736 KB Output is correct
9 Correct 30 ms 31736 KB Output is correct
10 Correct 37 ms 31736 KB Output is correct
11 Correct 30 ms 31736 KB Output is correct
12 Correct 31 ms 31608 KB Output is correct
13 Correct 30 ms 31736 KB Output is correct
14 Correct 31 ms 31612 KB Output is correct
15 Correct 30 ms 31736 KB Output is correct
16 Correct 37 ms 31736 KB Output is correct
17 Correct 31 ms 31736 KB Output is correct
18 Correct 31 ms 31720 KB Output is correct
19 Correct 31 ms 31736 KB Output is correct
20 Correct 31 ms 31608 KB Output is correct
21 Correct 30 ms 31608 KB Output is correct
22 Correct 31 ms 31736 KB Output is correct
23 Correct 30 ms 31736 KB Output is correct
24 Correct 31 ms 31608 KB Output is correct
25 Correct 31 ms 31736 KB Output is correct
26 Correct 31 ms 31736 KB Output is correct
27 Correct 78 ms 33336 KB Output is correct
28 Correct 68 ms 33124 KB Output is correct
29 Correct 76 ms 33248 KB Output is correct
30 Correct 70 ms 33392 KB Output is correct
31 Correct 81 ms 33392 KB Output is correct
32 Correct 68 ms 33140 KB Output is correct
33 Correct 77 ms 33396 KB Output is correct
34 Correct 70 ms 33268 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31608 KB Output is correct
2 Correct 31 ms 31608 KB Output is correct
3 Correct 31 ms 31608 KB Output is correct
4 Correct 31 ms 31732 KB Output is correct
5 Correct 30 ms 31620 KB Output is correct
6 Correct 31 ms 31608 KB Output is correct
7 Correct 30 ms 31736 KB Output is correct
8 Correct 31 ms 31736 KB Output is correct
9 Correct 30 ms 31736 KB Output is correct
10 Correct 37 ms 31736 KB Output is correct
11 Correct 30 ms 31736 KB Output is correct
12 Correct 31 ms 31608 KB Output is correct
13 Correct 30 ms 31736 KB Output is correct
14 Correct 31 ms 31612 KB Output is correct
15 Correct 30 ms 31736 KB Output is correct
16 Correct 37 ms 31736 KB Output is correct
17 Correct 31 ms 31736 KB Output is correct
18 Correct 31 ms 31720 KB Output is correct
19 Correct 31 ms 31736 KB Output is correct
20 Correct 31 ms 31608 KB Output is correct
21 Correct 30 ms 31608 KB Output is correct
22 Correct 31 ms 31736 KB Output is correct
23 Correct 30 ms 31736 KB Output is correct
24 Correct 31 ms 31608 KB Output is correct
25 Correct 31 ms 31736 KB Output is correct
26 Correct 31 ms 31736 KB Output is correct
27 Correct 78 ms 33336 KB Output is correct
28 Correct 68 ms 33124 KB Output is correct
29 Correct 76 ms 33248 KB Output is correct
30 Correct 70 ms 33392 KB Output is correct
31 Correct 81 ms 33392 KB Output is correct
32 Correct 68 ms 33140 KB Output is correct
33 Correct 77 ms 33396 KB Output is correct
34 Correct 70 ms 33268 KB Output is correct
35 Correct 181 ms 33476 KB Output is correct
36 Correct 184 ms 33460 KB Output is correct
37 Correct 181 ms 33392 KB Output is correct
38 Correct 180 ms 33392 KB Output is correct
39 Correct 183 ms 33392 KB Output is correct
40 Correct 152 ms 33524 KB Output is correct
41 Correct 150 ms 33524 KB Output is correct
42 Correct 141 ms 33416 KB Output is correct
43 Correct 139 ms 33464 KB Output is correct
44 Correct 150 ms 33528 KB Output is correct
45 Correct 151 ms 33576 KB Output is correct
46 Correct 142 ms 33524 KB Output is correct
47 Correct 142 ms 33396 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31608 KB Output is correct
2 Correct 31 ms 31608 KB Output is correct
3 Correct 31 ms 31608 KB Output is correct
4 Correct 31 ms 31732 KB Output is correct
5 Correct 30 ms 31620 KB Output is correct
6 Correct 31 ms 31608 KB Output is correct
7 Correct 30 ms 31736 KB Output is correct
8 Correct 31 ms 31736 KB Output is correct
9 Correct 30 ms 31736 KB Output is correct
10 Correct 37 ms 31736 KB Output is correct
11 Correct 30 ms 31736 KB Output is correct
12 Correct 31 ms 31608 KB Output is correct
13 Correct 30 ms 31736 KB Output is correct
14 Correct 31 ms 31612 KB Output is correct
15 Correct 30 ms 31736 KB Output is correct
16 Correct 37 ms 31736 KB Output is correct
17 Correct 31 ms 31736 KB Output is correct
18 Correct 31 ms 31720 KB Output is correct
19 Correct 31 ms 31736 KB Output is correct
20 Correct 31 ms 31608 KB Output is correct
21 Correct 30 ms 31608 KB Output is correct
22 Correct 31 ms 31736 KB Output is correct
23 Correct 30 ms 31736 KB Output is correct
24 Correct 31 ms 31608 KB Output is correct
25 Correct 31 ms 31736 KB Output is correct
26 Correct 31 ms 31736 KB Output is correct
27 Correct 78 ms 33336 KB Output is correct
28 Correct 68 ms 33124 KB Output is correct
29 Correct 76 ms 33248 KB Output is correct
30 Correct 70 ms 33392 KB Output is correct
31 Correct 81 ms 33392 KB Output is correct
32 Correct 68 ms 33140 KB Output is correct
33 Correct 77 ms 33396 KB Output is correct
34 Correct 70 ms 33268 KB Output is correct
35 Correct 181 ms 33476 KB Output is correct
36 Correct 184 ms 33460 KB Output is correct
37 Correct 181 ms 33392 KB Output is correct
38 Correct 180 ms 33392 KB Output is correct
39 Correct 183 ms 33392 KB Output is correct
40 Correct 152 ms 33524 KB Output is correct
41 Correct 150 ms 33524 KB Output is correct
42 Correct 141 ms 33416 KB Output is correct
43 Correct 139 ms 33464 KB Output is correct
44 Correct 150 ms 33528 KB Output is correct
45 Correct 151 ms 33576 KB Output is correct
46 Correct 142 ms 33524 KB Output is correct
47 Correct 142 ms 33396 KB Output is correct
48 Correct 2089 ms 46904 KB Output is correct
49 Correct 2101 ms 46820 KB Output is correct
50 Correct 2193 ms 46844 KB Output is correct
51 Correct 1843 ms 46804 KB Output is correct
52 Correct 1651 ms 45896 KB Output is correct
53 Correct 1539 ms 46176 KB Output is correct
54 Correct 1364 ms 45084 KB Output is correct
55 Correct 1346 ms 44896 KB Output is correct
56 Correct 1293 ms 44648 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31608 KB Output is correct
2 Correct 31 ms 31608 KB Output is correct
3 Correct 31 ms 31608 KB Output is correct
4 Correct 31 ms 31732 KB Output is correct
5 Correct 30 ms 31620 KB Output is correct
6 Correct 31 ms 31608 KB Output is correct
7 Correct 30 ms 31736 KB Output is correct
8 Correct 31 ms 31736 KB Output is correct
9 Correct 30 ms 31736 KB Output is correct
10 Correct 37 ms 31736 KB Output is correct
11 Correct 30 ms 31736 KB Output is correct
12 Correct 31 ms 31608 KB Output is correct
13 Correct 30 ms 31736 KB Output is correct
14 Correct 31 ms 31612 KB Output is correct
15 Correct 30 ms 31736 KB Output is correct
16 Correct 37 ms 31736 KB Output is correct
17 Correct 31 ms 31736 KB Output is correct
18 Correct 31 ms 31720 KB Output is correct
19 Correct 31 ms 31736 KB Output is correct
20 Correct 31 ms 31608 KB Output is correct
21 Correct 30 ms 31608 KB Output is correct
22 Correct 31 ms 31736 KB Output is correct
23 Correct 30 ms 31736 KB Output is correct
24 Correct 31 ms 31608 KB Output is correct
25 Correct 31 ms 31736 KB Output is correct
26 Correct 31 ms 31736 KB Output is correct
27 Correct 78 ms 33336 KB Output is correct
28 Correct 68 ms 33124 KB Output is correct
29 Correct 76 ms 33248 KB Output is correct
30 Correct 70 ms 33392 KB Output is correct
31 Correct 81 ms 33392 KB Output is correct
32 Correct 68 ms 33140 KB Output is correct
33 Correct 77 ms 33396 KB Output is correct
34 Correct 70 ms 33268 KB Output is correct
35 Correct 181 ms 33476 KB Output is correct
36 Correct 184 ms 33460 KB Output is correct
37 Correct 181 ms 33392 KB Output is correct
38 Correct 180 ms 33392 KB Output is correct
39 Correct 183 ms 33392 KB Output is correct
40 Correct 152 ms 33524 KB Output is correct
41 Correct 150 ms 33524 KB Output is correct
42 Correct 141 ms 33416 KB Output is correct
43 Correct 139 ms 33464 KB Output is correct
44 Correct 150 ms 33528 KB Output is correct
45 Correct 151 ms 33576 KB Output is correct
46 Correct 142 ms 33524 KB Output is correct
47 Correct 142 ms 33396 KB Output is correct
48 Correct 2089 ms 46904 KB Output is correct
49 Correct 2101 ms 46820 KB Output is correct
50 Correct 2193 ms 46844 KB Output is correct
51 Correct 1843 ms 46804 KB Output is correct
52 Correct 1651 ms 45896 KB Output is correct
53 Correct 1539 ms 46176 KB Output is correct
54 Correct 1364 ms 45084 KB Output is correct
55 Correct 1346 ms 44896 KB Output is correct
56 Correct 1293 ms 44648 KB Output is correct
57 Execution timed out 2552 ms 121900 KB Time limit exceeded
58 Halted 0 ms 0 KB -