QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#576947#9229. Juliet Unifies Onesqwqpmp#WA 0ms3620kbC++171.6kb2024-09-19 23:30:282024-09-19 23:30:29

Judging History

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

  • [2024-09-19 23:30:29]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3620kb
  • [2024-09-19 23:30:28]
  • 提交

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;
	auto calc=[&](string s)->int{
		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));
				len+=(j-i),i=j-1;
			}
		}
		if (!len) return 0;
		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--) {
			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].se-ls[i].fi+1);
				ans-=(ls[i+1].fi-ls[i].se-1);
				l++;
			}
			else break;
		}
		ans=min(ans,len);
		return ans;
	};
	int ans=calc(s);
	reverse(all(s));
	ans=min(ans,calc(s));
	cout<<ans<<endl;
}

详细

Test #1:

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

input:

00011011001

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

input:

11101111111111111101001011110111111110011101010110

output:

11

result:

ok 1 number(s): "11"

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3480kb

input:

00000000100000000000100000010001000

output:

-3

result:

wrong answer 1st numbers differ - expected: '3', found: '-3'