QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#673472#9430. Left Shifting 2yxfqlAC ✓7ms12204kbC++201.2kb2024-10-24 22:38:592024-10-24 22:38:59

Judging History

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

  • [2024-10-24 22:38:59]
  • 评测
  • 测评结果:AC
  • 用时:7ms
  • 内存:12204kb
  • [2024-10-24 22:38:59]
  • 提交

answer

#include<bits/stdc++.h>

using i64 = long long;
const int M=5e5+10;
int l[M<<1],r[M<<1];

void solve() {
    std::string s;
    std::cin >> s;
    	int n = s.length();
    	s = " " + s;
    	s.resize((n << 1) + 1);
    	for(int i = 1; i <= n; ++i) s[i + n] = s[i];
    	for(int i = 1; i < (n << 1); ++i)
    	{
    		if (s[i] == s[i - 1]) l[i] = l[i - 1];
    		else l[i] = i;
		}
		l[n << 1] = 0;
		for(int i = (n << 1) - 1; i; --i)
		{
			if (l[i] == l[i + 1]) r[i] = r[i + 1];
			else r[i] = i;
		}
		int cnt = 0;
		int minn = n + 1, ans = 0;
		for(int i = 1; i <= n; ++i)
		{
			if (l[i] == i) cnt += (std::min(r[i], n) - i + 1) >> 1; 
		}//cout << n << '\n';
		for(int i = 1; i <= n; ++i)
		{
			if (cnt < minn)
			{
				minn = cnt;
				ans = i - 1;
			} 
			//cout << i << " " << cnt << '\n'; 
			if (s[i] == s[i + 1] && ((r[i] - i + 1) & 1) == 0) --cnt;
			if (s[i + n - 1] == s[i + n] && ((i + n - l[i + n] + 1) & 1) == 0) ++cnt;
		}
		std::cout << minn << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin>>t;

    while(t--){
        solve();
    }

    return 0;
}

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

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5820kb

input:

3
abccbbbbd
abcde
x

output:

2
0
0

result:

ok 3 lines

Test #2:

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

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: 12204kb

input:

1
cbppzfsncqyzmuwrcvtxsciucxusskcjhaanwhqmyncytwhkubrvcqxgcehdxyewdyvpqjcmrnmlgrytrucexmmfulqbtfctehphmrzkosyvhtvjrromqncbgsjcwhmlqidkycaxyhsrduoxayntuhqubvboseeziwjvrfagsbvtxjjbexnajqapgxydwtztzbbdpoydnjipfizdfpmczgqvdmpvxbqubtygkfpdeonegfzsttirbhzkobbigwneyvtcxndfkljdvbbcfnadtfhgohfzqeidtgyandhnvb...

output:

18631

result:

ok single line: '18631'

Test #4:

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

input:

1
qokalgqjhyijyizyihdsiapbgvzxzevykavqmgqzrpjngciqcljsuplvpaziebmumatzvngwrhgsxrtcoiseihejwpewvosnrgvhoxluliuwixgxylazufebrwgfebazrkghgwbpqavehtnakmzqsetghmzoydwmeqvoplkyqngwrgktylrnaojpkvuwfsjbizedqwhfteyjobrglkhkeoxmxdgyuygawvdjhyakpkjchyxaqthrglcldevrzskdaotkbsbmnstrsxervdvmaylqxnwaecfmdszwedrdom...

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 3ms
memory: 11900kb

input:

1
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbyyqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhcccccccccccccccccccccccccccccccccccccccccccccccccccccccccccceeeeeeeeeeeeeeeeeeeeezzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...

output:

246800

result:

ok single line: '246800'

Test #6:

score: 0
Accepted
time: 7ms
memory: 12108kb

input:

1
yyyyyyyyyyyyyyyyyyyyyyyyhhhhhhhhaaaannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnhhhhhhhhhhhhhhhhhhhhhhhiiiiiiiieeeeeeeeeesssssssbbbbbbbbbbiiiiiiiwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxaaaaaaaaaaaaaaaadccccckkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkc...

output:

242729

result:

ok single line: '242729'

Extra Test:

score: 0
Extra Test Passed