ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#195891 | #3420. 对抗游戏 | cyqiu | 100 | 415ms | 13872kb | C++11 | 1.3kb | 2023-10-18 21:16:41 | 2023-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