UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#195891#3420. 对抗游戏cyqiu100415ms13872kbC++111.3kb2023-10-18 21:16:412023-10-18 22:45:21

answer

//#include<iostream>
//using namespace std;
//bool ishui[5001][5001];
//string s;
//int n,q;
//int main(){
//	cin >> n >> q;
//	cin >> s;
//	for(int i=0;i<n;i++){
//		ishui[i][i]=true;
//		ishui[i][i+1]=(s[i]==s[i+1]?true:false);
//	}
//	for(int step=3;step<=n;step++){
//		for(int l=0;l+step-1<n;l++){
//			int r=l+step-1;
//			if(s[l]==s[r])	ishui[l][r]=ishui[l+1][r-1];
//			else	ishui[l][r]=false;
//		}
//	}
//	while(q--){
//		int l,r;
//		cin >> l >> r;
//		if(ishui[l-1][r-1]){
//			cout << "Budada\n";
//		} else{
//			cout << ((r-l)%2==0?"Putata":"Budada") << '\n';
//		}
//	}
//	return 0;
//}
#include <bits/stdc++.h>
using namespace std;
const unsigned long long int base=2333;
const int N=1e6+3;
int Hash[N],Hash_reverse[N],power[N];
char s[N];
int main(){
	int q,l,r,n;
	scanf("%d %d\n%s",&n,&q,s+1);
	int slen=strlen(s+1);
	Hash[0]=0;
	Hash_reverse[0]=0;
	power[0]=1;
	for(int i=1;i<slen+1;i++){
		power[i]=power[i-1]*base;
	}
	for(int i=1;i<slen+1;i++){
		Hash[i]=Hash[i-1]*base+s[i]-'a'+1;
		Hash_reverse[i]=Hash_reverse[i-1]*base+s[slen-i+1]-'a'+1;
	}
	for(int i=0;i<q;i++){
		scanf("%d %d",&l,&r);
		if((Hash[r]-Hash[l-1]*power[r-l+1])==(Hash_reverse[slen-l+1]-Hash_reverse[slen-r]*power[r-l+1])){
			printf("Budada\n");
		}else{
			printf((r-l)%2==0?"Putata\n":"Budada\n");
		}
	}
	return 0;
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 1192kb

input:

10 10
lblbyybtft
5 6
1 3
7 7
1 3
1 3
8 10
4 4
7 10
3 5
7 9

output:

Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Putata
Putata

result:

ok 10 lines

Test #2:

score: 10
Accepted
time: 0ms
memory: 1188kb

input:

10 10
jjwwnnddhh
5 6
1 2
7 8
7 8
7 8
1 2
1 2
1 2
5 6
7 8

output:

Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada

result:

ok 10 lines

Test #3:

score: 10
Accepted
time: 0ms
memory: 1192kb

input:

10 10
qwqeemhmzx
2 6
9 9
6 7
9 9
1 3
7 8
6 8
10 10
2 10
2 6

output:

Putata
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Putata
Putata

result:

ok 10 lines

Test #4:

score: 10
Accepted
time: 0ms
memory: 1188kb

input:

10 10
mcmfpppppo
8 8
2 5
1 4
2 9
3 10
6 7
1 6
3 7
3 9
5 5

output:

Budada
Budada
Budada
Budada
Budada
Budada
Budada
Putata
Putata
Budada

result:

ok 10 lines

Test #5:

score: 10
Accepted
time: 0ms
memory: 1200kb

input:

1000 1000
egdbcjlrbuipkawdbhopiftkennnnektfipohbdwakpiubrljcbdgeofdbfqiuuiqfbdfoizwlorhtwrcganhbqspk...

output:

Putata
Putata
Budada
Budada
Putata
Putata
Putata
Putata
Putata
Budada
Putata
Putata
Budada
Budada
Pu...

result:

ok 1000 lines

Test #6:

score: 10
Accepted
time: 1ms
memory: 1204kb

input:

1000 1000
wuxigmyxyangcznnjctldollwhrlxxxurvfqhhqfvruxxxlrhwllodltcjnnzcgnayxymgixuwxgynrakxuiepswlk...

output:

Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Putata
Budada
Bu...

result:

ok 1000 lines

Test #7:

score: 10
Accepted
time: 1ms
memory: 1200kb

input:

1000 1000
ocyjgahmrewbwafqlrdwcvvmyjcwsijhocrdxcrylwwxspxijtdjjdtjixpsxwwlyrcxdrcohjiswcjymvvcwdrlqf...

output:

Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Bu...

result:

ok 1000 lines

Test #8:

score: 10
Accepted
time: 1ms
memory: 1204kb

input:

1000 1000
ytmyiamvpbtypwqpgtonwjeoejwnotgpqwpytbpvmaiymtyysjbjnjkqzrsrhhwjkmxqxesgkiybjeevxnqxklkqac...

output:

Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Bu...

result:

ok 1000 lines

Test #9:

score: 10
Accepted
time: 219ms
memory: 13868kb

input:

1000000 1000000
yfwuqhbatapgckxgynamtcotrqxcqcyrzvljxmzkhcwosomskmzhrolfojphwtrdxnhnpqzawsjdriqjmtph...

output:

Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Putata
Bu...

result:

ok 1000000 lines

Test #10:

score: 10
Accepted
time: 193ms
memory: 13872kb

input:

1000000 1000000
ntlhxklgvpuxdgmoajdozchlawxeemyxmruewqnhlycyxxgetzduqfhesxvllghacabbbdnbhpfrwycglgbx...

output:

Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Budada
Bu...

result:

ok 1000000 lines

Extra Test:

score: 0
Extra Test Passed