QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#740909#9430. Left Shifting 2xly_tyty#AC ✓5ms13232kbC++231.0kb2024-11-13 12:13:332024-11-13 12:13:33

Judging History

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

  • [2024-11-13 12:13:33]
  • 评测
  • 测评结果:AC
  • 用时:5ms
  • 内存:13232kb
  • [2024-11-13 12:13:33]
  • 提交

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=1;
	int cnt=0,res=0;;
	int ans=1e9;
	//cout<<s<<endl;
	for(int i=1;i<=2*n;i++)
	{
		if(i<=n)
		{
		if(i==1||s[i]==s[i-1])
		{
			res-=cnt/2;
			res+=(cnt+1)/2;
			q[r]=cnt+1;
			cnt++;
		}
		else{
			q[++r]=1;
			cnt=1;
		}
		}
		else{
			int ll=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[ll]==s[ll-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;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
abccbbbbd
abcde
x

output:

2
0
0

result:

ok 3 lines

Test #2:

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

input:

5000
lfpbavjsmppdppkfwnyfmbdhptdswsoulrbhyjh
cfliuqnynejgnxolzbdoztclzbozqomvioszk
eiivcoqoymonrqgrjdtkts
mdcvservaxcbioopfungsgkiftchwlmtbzqgaraovjknsgiegkvdbolmeunvrxrpscnf
ujeqtidwtoikkqtygo
llma
qjfvgwrdhaazejsfgilnpmmhkefndzvyon
kzwwpdpbrudqmwmjscllnnjyoepxophcoopvfepikouinuxx
vftculoorxskpkxoz...

output:

1
0
0
0
0
0
1
4
0
0
1
1
1
1
1
3
1
0
5
6
0
0
5
2
0
1
3
2
0
3
0
1
0
1
1
0
1
4
1
3
1
0
1
5
3
0
3
0
0
1
8
1
0
6
1
2
0
1
0
0
4
1
2
4
3
1
3
2
3
1
2
1
0
0
2
0
2
2
0
4
0
5
5
0
3
0
4
1
0
2
1
0
2
0
1
6
1
2
1
3
3
3
5
2
3
0
3
5
1
3
0
0
3
0
4
5
3
2
1
1
0
0
2
0
1
1
3
3
3
1
2
0
1
1
4
3
1
3
1
1
1
2
0
1
2
0
4
0
1
1
...

result:

ok 5000 lines

Test #3:

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

input:

1
cbppzfsncqyzmuwrcvtxsciucxusskcjhaanwhqmyncytwhkubrvcqxgcehdxyewdyvpqjcmrnmlgrytrucexmmfulqbtfctehphmrzkosyvhtvjrromqncbgsjcwhmlqidkycaxyhsrduoxayntuhqubvboseeziwjvrfagsbvtxjjbexnajqapgxydwtztzbbdpoydnjipfizdfpmczgqvdmpvxbqubtygkfpdeonegfzsttirbhzkobbigwneyvtcxndfkljdvbbcfnadtfhgohfzqeidtgyandhnvb...

output:

18631

result:

ok single line: '18631'

Test #4:

score: 0
Accepted
time: 5ms
memory: 12436kb

input:

1
qokalgqjhyijyizyihdsiapbgvzxzevykavqmgqzrpjngciqcljsuplvpaziebmumatzvngwrhgsxrtcoiseihejwpewvosnrgvhoxluliuwixgxylazufebrwgfebazrkghgwbpqavehtnakmzqsetghmzoydwmeqvoplkyqngwrgktylrnaojpkvuwfsjbizedqwhfteyjobrglkhkeoxmxdgyuygawvdjhyakpkjchyxaqthrglcldevrzskdaotkbsbmnstrsxervdvmaylqxnwaecfmdszwedrdom...

output:

0

result:

ok single line: '0'

Test #5:

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

input:

1
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbyyqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhcccccccccccccccccccccccccccccccccccccccccccccccccccccccccccceeeeeeeeeeeeeeeeeeeeezzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...

output:

246800

result:

ok single line: '246800'

Test #6:

score: 0
Accepted
time: 4ms
memory: 6396kb

input:

1
yyyyyyyyyyyyyyyyyyyyyyyyhhhhhhhhaaaannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnhhhhhhhhhhhhhhhhhhhhhhhiiiiiiiieeeeeeeeeesssssssbbbbbbbbbbiiiiiiiwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxaaaaaaaaaaaaaaaadccccckkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkc...

output:

242729

result:

ok single line: '242729'

Extra Test:

score: 0
Extra Test Passed