oj.uz

Submission #141086

# Submission time Handle Problem Language Result Execution time Memory
141086 2019-08-06T16:01:14 Z DrumpfTheGodEmperor Rope (JOI17_rope) C++14
80 / 100
 2500 ms 122680 KB 
#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

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()) {
   ^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31608 KB Output is correct
2 Correct 30 ms 31736 KB Output is correct
3 Correct 30 ms 31736 KB Output is correct
4 Correct 30 ms 31608 KB Output is correct
5 Correct 30 ms 31736 KB Output is correct
6 Correct 30 ms 31608 KB Output is correct
7 Correct 30 ms 31736 KB Output is correct
8 Correct 30 ms 31668 KB Output is correct
9 Correct 31 ms 31608 KB Output is correct
10 Correct 30 ms 31608 KB Output is correct
11 Correct 30 ms 31608 KB Output is correct
12 Correct 30 ms 31708 KB Output is correct
13 Correct 30 ms 31712 KB Output is correct
14 Correct 32 ms 31668 KB Output is correct
15 Correct 30 ms 31712 KB Output is correct
16 Correct 30 ms 31712 KB Output is correct
17 Correct 30 ms 31676 KB Output is correct
18 Correct 31 ms 31632 KB Output is correct
19 Correct 34 ms 31780 KB Output is correct
20 Correct 30 ms 31608 KB Output is correct
21 Correct 31 ms 31608 KB Output is correct
22 Correct 30 ms 31608 KB Output is correct
23 Correct 30 ms 31608 KB Output is correct
24 Correct 30 ms 31608 KB Output is correct
25 Correct 30 ms 31660 KB Output is correct
26 Correct 30 ms 31608 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 30 ms 31736 KB Output is correct
3 Correct 30 ms 31736 KB Output is correct
4 Correct 30 ms 31608 KB Output is correct
5 Correct 30 ms 31736 KB Output is correct
6 Correct 30 ms 31608 KB Output is correct
7 Correct 30 ms 31736 KB Output is correct
8 Correct 30 ms 31668 KB Output is correct
9 Correct 31 ms 31608 KB Output is correct
10 Correct 30 ms 31608 KB Output is correct
11 Correct 30 ms 31608 KB Output is correct
12 Correct 30 ms 31708 KB Output is correct
13 Correct 30 ms 31712 KB Output is correct
14 Correct 32 ms 31668 KB Output is correct
15 Correct 30 ms 31712 KB Output is correct
16 Correct 30 ms 31712 KB Output is correct
17 Correct 30 ms 31676 KB Output is correct
18 Correct 31 ms 31632 KB Output is correct
19 Correct 34 ms 31780 KB Output is correct
20 Correct 30 ms 31608 KB Output is correct
21 Correct 31 ms 31608 KB Output is correct
22 Correct 30 ms 31608 KB Output is correct
23 Correct 30 ms 31608 KB Output is correct
24 Correct 30 ms 31608 KB Output is correct
25 Correct 30 ms 31660 KB Output is correct
26 Correct 30 ms 31608 KB Output is correct
27 Correct 73 ms 33308 KB Output is correct
28 Correct 67 ms 33224 KB Output is correct
29 Correct 72 ms 33268 KB Output is correct
30 Correct 67 ms 33264 KB Output is correct
31 Correct 74 ms 33492 KB Output is correct
32 Correct 66 ms 33268 KB Output is correct
33 Correct 73 ms 33268 KB Output is correct
34 Correct 67 ms 33392 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 30 ms 31736 KB Output is correct
3 Correct 30 ms 31736 KB Output is correct
4 Correct 30 ms 31608 KB Output is correct
5 Correct 30 ms 31736 KB Output is correct
6 Correct 30 ms 31608 KB Output is correct
7 Correct 30 ms 31736 KB Output is correct
8 Correct 30 ms 31668 KB Output is correct
9 Correct 31 ms 31608 KB Output is correct
10 Correct 30 ms 31608 KB Output is correct
11 Correct 30 ms 31608 KB Output is correct
12 Correct 30 ms 31708 KB Output is correct
13 Correct 30 ms 31712 KB Output is correct
14 Correct 32 ms 31668 KB Output is correct
15 Correct 30 ms 31712 KB Output is correct
16 Correct 30 ms 31712 KB Output is correct
17 Correct 30 ms 31676 KB Output is correct
18 Correct 31 ms 31632 KB Output is correct
19 Correct 34 ms 31780 KB Output is correct
20 Correct 30 ms 31608 KB Output is correct
21 Correct 31 ms 31608 KB Output is correct
22 Correct 30 ms 31608 KB Output is correct
23 Correct 30 ms 31608 KB Output is correct
24 Correct 30 ms 31608 KB Output is correct
25 Correct 30 ms 31660 KB Output is correct
26 Correct 30 ms 31608 KB Output is correct
27 Correct 73 ms 33308 KB Output is correct
28 Correct 67 ms 33224 KB Output is correct
29 Correct 72 ms 33268 KB Output is correct
30 Correct 67 ms 33264 KB Output is correct
31 Correct 74 ms 33492 KB Output is correct
32 Correct 66 ms 33268 KB Output is correct
33 Correct 73 ms 33268 KB Output is correct
34 Correct 67 ms 33392 KB Output is correct
35 Correct 175 ms 33492 KB Output is correct
36 Correct 174 ms 33524 KB Output is correct
37 Correct 191 ms 33468 KB Output is correct
38 Correct 210 ms 33472 KB Output is correct
39 Correct 190 ms 33524 KB Output is correct
40 Correct 145 ms 33520 KB Output is correct
41 Correct 153 ms 33576 KB Output is correct
42 Correct 139 ms 33544 KB Output is correct
43 Correct 135 ms 33492 KB Output is correct
44 Correct 148 ms 33564 KB Output is correct
45 Correct 149 ms 33648 KB Output is correct
46 Correct 138 ms 33536 KB Output is correct
47 Correct 137 ms 33524 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 30 ms 31736 KB Output is correct
3 Correct 30 ms 31736 KB Output is correct
4 Correct 30 ms 31608 KB Output is correct
5 Correct 30 ms 31736 KB Output is correct
6 Correct 30 ms 31608 KB Output is correct
7 Correct 30 ms 31736 KB Output is correct
8 Correct 30 ms 31668 KB Output is correct
9 Correct 31 ms 31608 KB Output is correct
10 Correct 30 ms 31608 KB Output is correct
11 Correct 30 ms 31608 KB Output is correct
12 Correct 30 ms 31708 KB Output is correct
13 Correct 30 ms 31712 KB Output is correct
14 Correct 32 ms 31668 KB Output is correct
15 Correct 30 ms 31712 KB Output is correct
16 Correct 30 ms 31712 KB Output is correct
17 Correct 30 ms 31676 KB Output is correct
18 Correct 31 ms 31632 KB Output is correct
19 Correct 34 ms 31780 KB Output is correct
20 Correct 30 ms 31608 KB Output is correct
21 Correct 31 ms 31608 KB Output is correct
22 Correct 30 ms 31608 KB Output is correct
23 Correct 30 ms 31608 KB Output is correct
24 Correct 30 ms 31608 KB Output is correct
25 Correct 30 ms 31660 KB Output is correct
26 Correct 30 ms 31608 KB Output is correct
27 Correct 73 ms 33308 KB Output is correct
28 Correct 67 ms 33224 KB Output is correct
29 Correct 72 ms 33268 KB Output is correct
30 Correct 67 ms 33264 KB Output is correct
31 Correct 74 ms 33492 KB Output is correct
32 Correct 66 ms 33268 KB Output is correct
33 Correct 73 ms 33268 KB Output is correct
34 Correct 67 ms 33392 KB Output is correct
35 Correct 175 ms 33492 KB Output is correct
36 Correct 174 ms 33524 KB Output is correct
37 Correct 191 ms 33468 KB Output is correct
38 Correct 210 ms 33472 KB Output is correct
39 Correct 190 ms 33524 KB Output is correct
40 Correct 145 ms 33520 KB Output is correct
41 Correct 153 ms 33576 KB Output is correct
42 Correct 139 ms 33544 KB Output is correct
43 Correct 135 ms 33492 KB Output is correct
44 Correct 148 ms 33564 KB Output is correct
45 Correct 149 ms 33648 KB Output is correct
46 Correct 138 ms 33536 KB Output is correct
47 Correct 137 ms 33524 KB Output is correct
48 Correct 2011 ms 47500 KB Output is correct
49 Correct 2108 ms 47476 KB Output is correct
50 Correct 2081 ms 47428 KB Output is correct
51 Correct 1961 ms 47364 KB Output is correct
52 Correct 1592 ms 46528 KB Output is correct
53 Correct 1500 ms 46692 KB Output is correct
54 Correct 1392 ms 45644 KB Output is correct
55 Correct 1305 ms 45516 KB Output is correct
56 Correct 1264 ms 45280 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 30 ms 31736 KB Output is correct
3 Correct 30 ms 31736 KB Output is correct
4 Correct 30 ms 31608 KB Output is correct
5 Correct 30 ms 31736 KB Output is correct
6 Correct 30 ms 31608 KB Output is correct
7 Correct 30 ms 31736 KB Output is correct
8 Correct 30 ms 31668 KB Output is correct
9 Correct 31 ms 31608 KB Output is correct
10 Correct 30 ms 31608 KB Output is correct
11 Correct 30 ms 31608 KB Output is correct
12 Correct 30 ms 31708 KB Output is correct
13 Correct 30 ms 31712 KB Output is correct
14 Correct 32 ms 31668 KB Output is correct
15 Correct 30 ms 31712 KB Output is correct
16 Correct 30 ms 31712 KB Output is correct
17 Correct 30 ms 31676 KB Output is correct
18 Correct 31 ms 31632 KB Output is correct
19 Correct 34 ms 31780 KB Output is correct
20 Correct 30 ms 31608 KB Output is correct
21 Correct 31 ms 31608 KB Output is correct
22 Correct 30 ms 31608 KB Output is correct
23 Correct 30 ms 31608 KB Output is correct
24 Correct 30 ms 31608 KB Output is correct
25 Correct 30 ms 31660 KB Output is correct
26 Correct 30 ms 31608 KB Output is correct
27 Correct 73 ms 33308 KB Output is correct
28 Correct 67 ms 33224 KB Output is correct
29 Correct 72 ms 33268 KB Output is correct
30 Correct 67 ms 33264 KB Output is correct
31 Correct 74 ms 33492 KB Output is correct
32 Correct 66 ms 33268 KB Output is correct
33 Correct 73 ms 33268 KB Output is correct
34 Correct 67 ms 33392 KB Output is correct
35 Correct 175 ms 33492 KB Output is correct
36 Correct 174 ms 33524 KB Output is correct
37 Correct 191 ms 33468 KB Output is correct
38 Correct 210 ms 33472 KB Output is correct
39 Correct 190 ms 33524 KB Output is correct
40 Correct 145 ms 33520 KB Output is correct
41 Correct 153 ms 33576 KB Output is correct
42 Correct 139 ms 33544 KB Output is correct
43 Correct 135 ms 33492 KB Output is correct
44 Correct 148 ms 33564 KB Output is correct
45 Correct 149 ms 33648 KB Output is correct
46 Correct 138 ms 33536 KB Output is correct
47 Correct 137 ms 33524 KB Output is correct
48 Correct 2011 ms 47500 KB Output is correct
49 Correct 2108 ms 47476 KB Output is correct
50 Correct 2081 ms 47428 KB Output is correct
51 Correct 1961 ms 47364 KB Output is correct
52 Correct 1592 ms 46528 KB Output is correct
53 Correct 1500 ms 46692 KB Output is correct
54 Correct 1392 ms 45644 KB Output is correct
55 Correct 1305 ms 45516 KB Output is correct
56 Correct 1264 ms 45280 KB Output is correct
57 Execution timed out 2594 ms 122680 KB Time limit exceeded
58 Halted 0 ms 0 KB -