QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#576905#9229. Juliet Unifies Onesqwqpmp#RE 0ms3880kbC++171.5kb2024-09-19 23:17:082024-09-19 23:17:09

Judging History

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

  • [2024-09-19 23:17:09]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3880kb
  • [2024-09-19 23:17:08]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define endl '\n'
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand()%x; }
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
// head

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);

	string s; cin>>s;
	vector<pii> ls;
	int len=0;
	for (int i=0,j=0;i<SZ(s);i++) {
		if (s[i]=='1') {
			j=i; while (s[j]=='1' and j<SZ(s)) j++;
			ls.pb(mp(i,j-1));
			cerr<<i<<" "<<j-1<<endl;
			len+=(j-i),i=j-1;
		}
	}
	int ans=(ls.back()).se-(ls[0]).fi+1-len;
	int r=SZ(ls)-1,l=0;
	for (int i=SZ(ls)-1;i>0;i--) {
		cerr<<(ls[i].fi-ls[i-1].se-1)<<" "<<(ls[i].se-ls[i].fi+1)<<endl;
		if (ls[i].fi-ls[i-1].se-1>=ls[i].se-ls[i].fi+1) {
			ans+=(ls[i].se-ls[i].fi+1);
			ans-=(ls[i].fi-ls[i-1].se-1);
			r--;
		} 
		else break;
	}
	for (int i=0;i<r;i++) {
		if (ls[i+1].fi-ls[i].se-1>=ls[i].se-ls[i].fi+1) {
			ans+=(ls[i+1].se-ls[i].fi+1);
			ans-=(ls[i].fi-ls[i-1].se-1);
			l++;
		}
		else break;
	}
	ans=min(ans,len);
	cout<<ans<<endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

00011011001

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

input:

11101111111111111101001011110111111110011101010110

output:

11

result:

ok 1 number(s): "11"

Test #3:

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

input:

00000000100000000000100000010001000

output:

3

result:

ok 1 number(s): "3"

Test #4:

score: -100
Runtime Error

input:

00000000000000000000000000000000000000000000000000

output:


result: