답안 #545761

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
545761	2022-04-05T11:47:53 Z	Koosha_mv	Monochrome Points (JOI20_monochrome)	C++14	35 / 100	398 ms	7380 KB

monochrome

#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=4e5+99;

int n,t,ans,a[N],L[N],R[N],fenwik[N];
string s;
vector<int> vec0,vec1;

void add(int x, int val){ for (x++;x>0;x-=x&-x) fenwik[x]+=val; }
int get(int x) { int res=0; for(x++;x<N;x+=x&-x) res+=fenwik[x]; return res; }

bool check(int lx,int rx,int ly,int ry){
	if(lx>rx) swap(lx,rx);
	if(ly>ry) swap(ly,ry);
	if(lx>ly) swap(lx,ly),swap(rx,ry);
	return ly<rx && rx<ry;
}
int calc(int shift){
	f(i,0,N) fenwik[i]=0;
	int res=0;
	f(i,0,n){
		L[i]=min(vec0[i],vec1[(i+shift)%n]);
		R[i]=max(vec0[i],vec1[(i+shift)%n]);
		a[L[i]]=i;
		a[R[i]]=i;
	}
	f(i,0,2*n){
		if(L[a[i]]==i){
			add(i,1);
		}
		else{
			add(L[a[i]],-1);
			res+=get(L[a[i]]);
		}
	}
	return res;
}

int32_t main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n>>s;
	f(i,0,2*n) if(s[i]==s[0]) vec0.pb(i); else vec1.pb(i);
	int l=-1,r=n-1;
	while(l+1<r){
		int mid=(l+r)>>1;
		if(calc(mid)<calc(mid+1)){
			l=mid;
		}
		else{
			r=mid;
		}
	}
	cout<<calc(r);
}

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1876 KB	Output is correct
2	Correct	1 ms	1876 KB	Output is correct
3	Correct	1 ms	1876 KB	Output is correct
4	Correct	1 ms	1876 KB	Output is correct
5	Correct	1 ms	1876 KB	Output is correct
6	Correct	2 ms	1876 KB	Output is correct
7	Correct	1 ms	1876 KB	Output is correct
8	Correct	2 ms	1876 KB	Output is correct
9	Correct	1 ms	1876 KB	Output is correct
10	Correct	1 ms	1876 KB	Output is correct
11	Correct	1 ms	1876 KB	Output is correct
12	Correct	1 ms	1876 KB	Output is correct
13	Correct	1 ms	1876 KB	Output is correct

Subtask #2
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1876 KB	Output is correct
2	Correct	1 ms	1876 KB	Output is correct
3	Correct	1 ms	1876 KB	Output is correct
4	Correct	1 ms	1876 KB	Output is correct
5	Correct	1 ms	1876 KB	Output is correct
6	Correct	2 ms	1876 KB	Output is correct
7	Correct	1 ms	1876 KB	Output is correct
8	Correct	2 ms	1876 KB	Output is correct
9	Correct	1 ms	1876 KB	Output is correct
10	Correct	1 ms	1876 KB	Output is correct
11	Correct	1 ms	1876 KB	Output is correct
12	Correct	1 ms	1876 KB	Output is correct
13	Correct	1 ms	1876 KB	Output is correct
14	Correct	3 ms	1876 KB	Output is correct
15	Correct	2 ms	1876 KB	Output is correct
16	Correct	2 ms	1876 KB	Output is correct
17	Correct	2 ms	1876 KB	Output is correct
18	Correct	2 ms	1876 KB	Output is correct
19	Correct	2 ms	1876 KB	Output is correct
20	Correct	2 ms	1876 KB	Output is correct
21	Correct	2 ms	1888 KB	Output is correct
22	Correct	2 ms	1876 KB	Output is correct
23	Correct	2 ms	1876 KB	Output is correct
24	Correct	2 ms	1876 KB	Output is correct
25	Correct	2 ms	1876 KB	Output is correct
26	Correct	2 ms	1876 KB	Output is correct
27	Correct	2 ms	1876 KB	Output is correct
28	Correct	2 ms	1876 KB	Output is correct
29	Correct	2 ms	1876 KB	Output is correct
30	Correct	2 ms	1876 KB	Output is correct
31	Correct	2 ms	1876 KB	Output is correct
32	Correct	2 ms	1876 KB	Output is correct
33	Correct	2 ms	1876 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1876 KB	Output is correct
2	Correct	1 ms	1876 KB	Output is correct
3	Correct	1 ms	1876 KB	Output is correct
4	Correct	1 ms	1876 KB	Output is correct
5	Correct	1 ms	1876 KB	Output is correct
6	Correct	2 ms	1876 KB	Output is correct
7	Correct	1 ms	1876 KB	Output is correct
8	Correct	2 ms	1876 KB	Output is correct
9	Correct	1 ms	1876 KB	Output is correct
10	Correct	1 ms	1876 KB	Output is correct
11	Correct	1 ms	1876 KB	Output is correct
12	Correct	1 ms	1876 KB	Output is correct
13	Correct	1 ms	1876 KB	Output is correct
14	Correct	3 ms	1876 KB	Output is correct
15	Correct	2 ms	1876 KB	Output is correct
16	Correct	2 ms	1876 KB	Output is correct
17	Correct	2 ms	1876 KB	Output is correct
18	Correct	2 ms	1876 KB	Output is correct
19	Correct	2 ms	1876 KB	Output is correct
20	Correct	2 ms	1876 KB	Output is correct
21	Correct	2 ms	1888 KB	Output is correct
22	Correct	2 ms	1876 KB	Output is correct
23	Correct	2 ms	1876 KB	Output is correct
24	Correct	2 ms	1876 KB	Output is correct
25	Correct	2 ms	1876 KB	Output is correct
26	Correct	2 ms	1876 KB	Output is correct
27	Correct	2 ms	1876 KB	Output is correct
28	Correct	2 ms	1876 KB	Output is correct
29	Correct	2 ms	1876 KB	Output is correct
30	Correct	2 ms	1876 KB	Output is correct
31	Correct	2 ms	1876 KB	Output is correct
32	Correct	2 ms	1876 KB	Output is correct
33	Correct	2 ms	1876 KB	Output is correct
34	Correct	4 ms	1876 KB	Output is correct
35	Correct	4 ms	1876 KB	Output is correct
36	Correct	4 ms	1876 KB	Output is correct
37	Correct	4 ms	1876 KB	Output is correct
38	Correct	4 ms	1876 KB	Output is correct
39	Correct	4 ms	1876 KB	Output is correct
40	Correct	3 ms	1876 KB	Output is correct
41	Correct	4 ms	1876 KB	Output is correct
42	Correct	4 ms	1876 KB	Output is correct
43	Correct	4 ms	1876 KB	Output is correct
44	Correct	4 ms	1964 KB	Output is correct
45	Correct	4 ms	1876 KB	Output is correct
46	Correct	4 ms	1876 KB	Output is correct
47	Correct	4 ms	1876 KB	Output is correct
48	Correct	4 ms	1876 KB	Output is correct
49	Correct	4 ms	1876 KB	Output is correct
50	Correct	4 ms	1876 KB	Output is correct
51	Correct	4 ms	1876 KB	Output is correct
52	Correct	4 ms	1876 KB	Output is correct

Subtask #4
0.0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1876 KB	Output is correct
2	Correct	1 ms	1876 KB	Output is correct
3	Correct	1 ms	1876 KB	Output is correct
4	Correct	1 ms	1876 KB	Output is correct
5	Correct	1 ms	1876 KB	Output is correct
6	Correct	2 ms	1876 KB	Output is correct
7	Correct	1 ms	1876 KB	Output is correct
8	Correct	2 ms	1876 KB	Output is correct
9	Correct	1 ms	1876 KB	Output is correct
10	Correct	1 ms	1876 KB	Output is correct
11	Correct	1 ms	1876 KB	Output is correct
12	Correct	1 ms	1876 KB	Output is correct
13	Correct	1 ms	1876 KB	Output is correct
14	Correct	3 ms	1876 KB	Output is correct
15	Correct	2 ms	1876 KB	Output is correct
16	Correct	2 ms	1876 KB	Output is correct
17	Correct	2 ms	1876 KB	Output is correct
18	Correct	2 ms	1876 KB	Output is correct
19	Correct	2 ms	1876 KB	Output is correct
20	Correct	2 ms	1876 KB	Output is correct
21	Correct	2 ms	1888 KB	Output is correct
22	Correct	2 ms	1876 KB	Output is correct
23	Correct	2 ms	1876 KB	Output is correct
24	Correct	2 ms	1876 KB	Output is correct
25	Correct	2 ms	1876 KB	Output is correct
26	Correct	2 ms	1876 KB	Output is correct
27	Correct	2 ms	1876 KB	Output is correct
28	Correct	2 ms	1876 KB	Output is correct
29	Correct	2 ms	1876 KB	Output is correct
30	Correct	2 ms	1876 KB	Output is correct
31	Correct	2 ms	1876 KB	Output is correct
32	Correct	2 ms	1876 KB	Output is correct
33	Correct	2 ms	1876 KB	Output is correct
34	Correct	4 ms	1876 KB	Output is correct
35	Correct	4 ms	1876 KB	Output is correct
36	Correct	4 ms	1876 KB	Output is correct
37	Correct	4 ms	1876 KB	Output is correct
38	Correct	4 ms	1876 KB	Output is correct
39	Correct	4 ms	1876 KB	Output is correct
40	Correct	3 ms	1876 KB	Output is correct
41	Correct	4 ms	1876 KB	Output is correct
42	Correct	4 ms	1876 KB	Output is correct
43	Correct	4 ms	1876 KB	Output is correct
44	Correct	4 ms	1964 KB	Output is correct
45	Correct	4 ms	1876 KB	Output is correct
46	Correct	4 ms	1876 KB	Output is correct
47	Correct	4 ms	1876 KB	Output is correct
48	Correct	4 ms	1876 KB	Output is correct
49	Correct	4 ms	1876 KB	Output is correct
50	Correct	4 ms	1876 KB	Output is correct
51	Correct	4 ms	1876 KB	Output is correct
52	Correct	4 ms	1876 KB	Output is correct
53	Incorrect	398 ms	7380 KB	Output isn't correct
54	Halted	0 ms	0 KB	-

답안 #545761

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 21.0 / 21.0

Subtask #3 10.0 / 10.0

Subtask #4 0.0 / 65.0

Subtask #1
4.0 / 4.0

Subtask #2
21.0 / 21.0

Subtask #3
10.0 / 10.0

Subtask #4
0.0 / 65.0