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
#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;
}
# 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
# 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 -
# 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 -
# 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 -