QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#576947 | #9229. Juliet Unifies Ones | qwqpmp# | WA | 0ms | 3620kb | C++17 | 1.6kb | 2024-09-19 23:30:28 | 2024-09-19 23:30:29 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'