QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#595390#9229. Juliet Unifies Onesucup-team4975#AC ✓0ms4092kbC++141.3kb2024-09-28 13:36:262024-09-28 13:36:26

Judging History

你现在查看的是最新测评结果

  • [2024-09-28 13:36:26]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:4092kb
  • [2024-09-28 13:36:26]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<vector>
#include<queue>
#include<set>
using namespace std;

const int N=60;
int n,cnt,pre[N][2],suf[N][2];
char s[N];
deque<pair<int,char> >q;
pair<int,char>c[N];

inline void solve()
{
	int ans=0;
	scanf("%s",s+1);
	
	n=strlen(s+1);
	for(int i=1;i<=n;i++)
		if(s[i]=='1')ans++;
	for(int i=1;i<=n;)
	{
		int j=i;
		while(j+1<=n&&s[j+1]==s[i])j++;
		q.push_front(make_pair(j-i+1,s[i]));
		i=j+1;
	}
	if(q.size()&&q.front().second=='0')q.pop_front();
	if(q.size()&&q.back().second=='0')q.pop_back();
	if(!q.size())
	{
		puts("0");
		return;
	}
	cnt=0;
	for(auto pos:q)
		c[++cnt]=pos;
	//for(int i=1;i<=cnt;i++)
	//	cout<<c[i].first<<" "<<c[i].second<<endl;;

	for(int i=1;i<=cnt;i++)
	{
		if(c[i].second=='0')
			pre[i][0]=pre[i-1][0]+c[i].first,
			pre[i][1]=pre[i-1][1];
		else pre[i][0]=pre[i-1][0],
			pre[i][1]=pre[i-1][1]+c[i].first;
	}
	for(int i=1;i<=cnt;i++)
		for(int j=i;j<=cnt;j++)
			if(c[i].second=='1'&&c[j].second=='1')
				ans=min(ans,pre[j][0]-pre[i-1][0]+pre[i-1][1]+pre[cnt][1]-pre[j][1]);
	printf("%d\n",ans);
	for(int i=1;i<=n;i++)
		pre[i][0]=pre[i][1]=0;
}

signed main()
{
	int T;
	//scanf("%d",&T);
	T=1;
	while(T--)solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3796kb

input:

00011011001

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

11101111111111111101001011110111111110011101010110

output:

11

result:

ok 1 number(s): "11"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3740kb

input:

00000000100000000000100000010001000

output:

3

result:

ok 1 number(s): "3"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3732kb

input:

00000000000000000000000000000000000000000000000000

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

00000000100000000000100000011000

output:

2

result:

ok 1 number(s): "2"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

11000010100100000011101100000001000100000000000000

output:

8

result:

ok 1 number(s): "8"

Test #7:

score: 0
Accepted
time: 0ms
memory: 4020kb

input:

01100100111011110101010110000100001111110001110001

output:

19

result:

ok 1 number(s): "19"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

1110101111001

output:

3

result:

ok 1 number(s): "3"

Test #9:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

1

output:

0

result:

ok 1 number(s): "0"

Test #10:

score: 0
Accepted
time: 0ms
memory: 4084kb

input:

1001

output:

1

result:

ok 1 number(s): "1"

Test #11:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

11111111111111111111111111111111111111111111111111

output:

0

result:

ok 1 number(s): "0"

Test #12:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

11111100000000001101010101100011

output:

9

result:

ok 1 number(s): "9"

Test #13:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

00011011001

output:

2

result:

ok 1 number(s): "2"

Test #14:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

11011

output:

1

result:

ok 1 number(s): "1"

Test #15:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

100011011

output:

2

result:

ok 1 number(s): "2"

Test #16:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

0

output:

0

result:

ok 1 number(s): "0"

Test #17:

score: 0
Accepted
time: 0ms
memory: 4092kb

input:

1010101010011011001101100110011101101011100110110

output:

19

result:

ok 1 number(s): "19"

Test #18:

score: 0
Accepted
time: 0ms
memory: 4092kb

input:

01110100000000111100000011000000000110010001110101

output:

14

result:

ok 1 number(s): "14"

Test #19:

score: 0
Accepted
time: 0ms
memory: 4080kb

input:

01100001000000010000000000010010000100100101001000

output:

9

result:

ok 1 number(s): "9"

Test #20:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

1101010101010101010101010101010101010101010101011

output:

23

result:

ok 1 number(s): "23"

Extra Test:

score: 0
Extra Test Passed