Submission #294171

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
294171	2020-09-08T16:19:05 Z	pit4h	Monochrome Points (JOI20_monochrome)	C++14	4 / 100	1 ms	384 KB

monochrome

#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#ifndef LOCAL
#define cerr if(0)cerr
#endif
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
int n;
void inc(int& x) {
	x =  (x+1)%(2*n);	
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	string s; cin>>s;
	ll best = 0;
	int skipped = 0;
	for(int i=1; i<2*n; ++i) {
		if(s[i]==s[0]) {
			skipped++;
			continue;
		}
		if(abs(n/2-skipped)>5) continue;
		ll ans = 0;
		vector<bool> intersect(2*n, 1);
		int cnt = 1;
		vector<int> matched(2*n, -1);
		matched[0] = matched[i] = 0;
		int b = 1, w = i;			
		inc(w);	
		int iter = 1;
		while(iter<n) {
			while(s[b]!=s[0]) {
				if(matched[b] != -1) {
					intersect[matched[b]] = !intersect[matched[b]];
					if(intersect[matched[b]]) {
						cnt++;
					}
					else {
						cnt--;
					}
				}
				inc(b);
			}

			while(s[w]==s[0]) {
				if(matched[w] != -1) {
					intersect[w] = !intersect[w];
					if(intersect[w]) {
						cnt++;
					}
					else {
						cnt--;
					}
				}
				inc(w);
			}
			matched[b] = matched[w] = b;
			ans += cnt;
			cnt++;
			iter++;
			inc(b); inc(w);
		}
		cerr<<ans<<' '<<i<<'\n';
		best = max(best, ans);
	}
	cout<<best;
}

Subtask #1

4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	0 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	0 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	0 ms	384 KB	Output is correct
12	Correct	0 ms	384 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct

Subtask #2

0.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	0 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	0 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	0 ms	384 KB	Output is correct
12	Correct	0 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	1 ms	384 KB	Output is correct
16	Incorrect	1 ms	384 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #3

0.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	0 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	0 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	0 ms	384 KB	Output is correct
12	Correct	0 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	1 ms	384 KB	Output is correct
16	Incorrect	1 ms	384 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #4

0.0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	0 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	0 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	0 ms	384 KB	Output is correct
12	Correct	0 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	1 ms	384 KB	Output is correct
16	Incorrect	1 ms	384 KB	Output isn't correct
17	Halted	0 ms	0 KB	-