QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #740883 | #9430. Left Shifting 2 | xly_tyty# | WA | 0ms | 3744kb | C++23 | 939b | 2024-11-13 12:04:07 | 2024-11-13 12:04:07 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const long long N=1e6+10,mod=998244353,INF=1e15;
ll n,m,k,a[N];
bool st[N];
string s;
int q[N],l,r;
void solve()
{
cin>>s;
n=s.size();
s=s+s;
s=" "+s;
l=1,r=0;
int cnt=0,res=0;;
int ans=1e9;
for(int i=1;i<=2*n;i++)
{
if(i<=n)
{
if(i==1||s[i]==s[i-1])cnt++;
else{
q[++r]=cnt;
res+=cnt/2;
cnt=1;
}
}
else{
int l=i-n+1;
if(s[i]==s[i-1])
{
res-=cnt/2;
res+=(cnt+1)/2;
q[r]=cnt+1;
cnt++;
}
else{
q[++r]=1;
cnt=1;
}
if(s[l]==s[l-1])
{
res-=q[l]/2;
res+=(q[l]-1)/2;
q[l]--;
}
else l++;
}
if(i>=n)ans=min(ans,res);
}
cout<<ans<<endl;
}
signed main()
{
cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
int T;cin>>T;
while(T--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
input:
3 abccbbbbd abcde x
output:
2 0 0
result:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3744kb
input:
5000 lfpbavjsmppdppkfwnyfmbdhptdswsoulrbhyjh cfliuqnynejgnxolzbdoztclzbozqomvioszk eiivcoqoymonrqgrjdtkts mdcvservaxcbioopfungsgkiftchwlmtbzqgaraovjknsgiegkvdbolmeunvrxrpscnf ujeqtidwtoikkqtygo llma qjfvgwrdhaazejsfgilnpmmhkefndzvyon kzwwpdpbrudqmwmjscllnnjyoepxophcoopvfepikouinuxx vftculoorxskpkxoz...
output:
2 0 1 1 1 1 2 4 1 0 2 2 1 2 2 4 1 1 5 7 1 1 6 3 1 2 3 2 0 4 1 1 0 0 2 0 2 4 2 4 2 1 1 6 4 1 4 1 0 1 8 0 1 6 2 3 1 2 0 1 5 2 3 5 4 1 4 2 4 0 3 1 1 1 2 1 2 3 1 5 1 6 6 1 4 1 4 1 0 3 2 1 3 0 2 7 2 3 1 4 4 4 6 3 4 1 4 6 2 3 1 1 4 1 5 6 4 3 1 2 0 1 3 0 2 2 3 4 4 1 3 1 1 2 5 3 2 4 1 2 2 3 1 2 3 1 5 1 2 1 ...
result:
wrong answer 1st lines differ - expected: '1', found: '2'