Submission #256288

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
256288	2020-08-02T13:47:49 Z	pit4h	Rope (JOI17_rope)	C++14	0 / 100	1 ms	384 KB

rope

#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, m;
	cin>>n>>m;
	vector<int> a(n), occ(m+1);
	vector<vector<pair<int, int>>> col(m+1);
	vector<pair<int, int>> best;
	for(int i=0; i<n; ++i) {
		cin>>a[i];
		occ[a[i]]++;
		if(i==0 || a[i] != a[i-1]) {
			col[a[i]].push_back({i, i});
		}
		else {
			col[a[i]].back().nd = i;
		}
	}
	for(int i=1; i<=m; ++i) {
		best.push_back({occ[i], i});
	}
	sort(best.rbegin(), best.rend());
	for(int c=1; c<=m; ++c) {
		if(col[c].empty()) continue;
		vector<vector<int>> cnt(2, vector<int>(m+1));
		
		vector<int> prv(2);
		vector<bool> fail(2);

		int beg = col[c][0].st;
		int end = col[c][0].nd;
		if(end==n-1) {
			int ans = n;
			if(beg==0) ans = 0;
			else {
				if((end-beg+1)%2==1) {
					cnt[0][a[beg-1]] = 1;
				}
				for(int i=1; i<=m; ++i) {
					if(c==i) {
						ans = min(ans, n-occ[c]);
					}
					else {
						ans = min(ans, n - occ[c] - occ[i] + cnt[0][i]);
					}	
				}
			}
			cout<<ans<<'\n';
			continue;
		}
		if((end-beg+1)%2==1) {
			if(beg==0) {
				prv[0] = end;
				cnt[1][a[end+1]] = 1;
				prv[1] = end+1;
			}
			else {
				cnt[0][a[beg-1]] = 1;
				prv[0] = end;
				cnt[1][a[end+1]] = 1;
				prv[1] = end+1;
			}
		}
		else {
			if(beg==0) {
				prv[0] = end;
				cnt[1][a[end+1]] = 1;
				prv[1] = end+1;
			}
			else {
				prv[0] = end;
				cnt[1][a[beg-1]] = 1;
				cnt[1][a[end+1]] = 1;
				prv[1] = end+1;
			}
		}
		for(int it=0; it<=1; ++it) {
			bool start=0;
			for(auto cur: col[c]) {
				if(!start) {
					start=1;
					continue;
				}
				beg = cur.st;
				end = cur.nd;
				if((beg-prv[it])%2==0) {
					beg--;
					cnt[it][a[beg]]++;
				}
				if((end-beg+1)%2==1 && end != n-1) {
					end++;
					cnt[it][a[end]]++;
				}
				prv[it] = end;
			}
		}
		int ans = n;
		for(int i=1; i<=m; ++i) {
			if(c==i) {
				ans = min(ans, n-occ[c]);
			}
			else {
				if(!fail[0]) ans = min(ans, n - occ[c] - occ[i] + cnt[0][i]);
				if(!fail[1]) ans = min(ans, n - occ[c] - occ[i] + cnt[1][i]);
			}
		}
		cout<<ans<<'\n';
	}
}

Subtask #1
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	1 ms	384 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	1 ms	384 KB	Output is correct
15	Correct	0 ms	384 KB	Output is correct
16	Correct	1 ms	384 KB	Output is correct
17	Correct	0 ms	384 KB	Output is correct
18	Correct	1 ms	384 KB	Output is correct
19	Correct	1 ms	384 KB	Output is correct
20	Correct	1 ms	384 KB	Output is correct
21	Incorrect	0 ms	384 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #2
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	1 ms	384 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	1 ms	384 KB	Output is correct
15	Correct	0 ms	384 KB	Output is correct
16	Correct	1 ms	384 KB	Output is correct
17	Correct	0 ms	384 KB	Output is correct
18	Correct	1 ms	384 KB	Output is correct
19	Correct	1 ms	384 KB	Output is correct
20	Correct	1 ms	384 KB	Output is correct
21	Incorrect	0 ms	384 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	1 ms	384 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	1 ms	384 KB	Output is correct
15	Correct	0 ms	384 KB	Output is correct
16	Correct	1 ms	384 KB	Output is correct
17	Correct	0 ms	384 KB	Output is correct
18	Correct	1 ms	384 KB	Output is correct
19	Correct	1 ms	384 KB	Output is correct
20	Correct	1 ms	384 KB	Output is correct
21	Incorrect	0 ms	384 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #4
0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	1 ms	384 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	1 ms	384 KB	Output is correct
15	Correct	0 ms	384 KB	Output is correct
16	Correct	1 ms	384 KB	Output is correct
17	Correct	0 ms	384 KB	Output is correct
18	Correct	1 ms	384 KB	Output is correct
19	Correct	1 ms	384 KB	Output is correct
20	Correct	1 ms	384 KB	Output is correct
21	Incorrect	0 ms	384 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	1 ms	384 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	1 ms	384 KB	Output is correct
15	Correct	0 ms	384 KB	Output is correct
16	Correct	1 ms	384 KB	Output is correct
17	Correct	0 ms	384 KB	Output is correct
18	Correct	1 ms	384 KB	Output is correct
19	Correct	1 ms	384 KB	Output is correct
20	Correct	1 ms	384 KB	Output is correct
21	Incorrect	0 ms	384 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Submission #256288

Compilation message

Subtask #1 0 / 15.0

Subtask #2 0 / 30.0

Subtask #3 0 / 10.0

Subtask #4 0 / 25.0

Subtask #5 0 / 20.0

Subtask #1
0 / 15.0

Subtask #2
0 / 30.0

Subtask #3
0 / 10.0

Subtask #4
0 / 25.0

Subtask #5
0 / 20.0