Submission #1225774
Source Code Expand
#include <bits/stdc++.h>
#define N 512202
using namespace std;
const int _1[13] = {19, 41, 43, 71, 97, 199, 293, 359, 661, 1201, 4493, 8111, 8527};
const int _2[17] = {1009, 1093, 1201, 1847, 2357, 2657, 2963, 4507,
4721, 5039, 5227, 5471, 5783, 5927, 6469, 7307, 8563};
const int z1[17] = {1949639529, 286828591, 506243666, 613426512, 565176353,
1732683515, 456216594, 856761466, 516876564, 321786342, 807132947,
321947198, 759807980, 679807890, 837504983, 216798076, 598097298};
const int z2[13] = {719032874, 1932598019, 804759801, 732947698,
690745973, 219476215, 964598032, 649803217, 498032170,
439807586, 587436980, 321754981, 759874319};
bool flag;
int n, i;
int Q, l, r;
int f[N][27];
int st[N], pt;
char s[N];
char hmap[0x1000000];
string t;
int getHcode(string &str){
int i, len = str.length();
int h1 = 0, h2 = 0;
for(i = 0; i < len; i++){
h1 = h1 * _1[i % 13] + z1[i % 17] + str[i];
h2 = h2 * _2[i % 17] + z2[i % 13] + str[i];
h1 ^= h2 << 1;
h2 ^= h1 << 1;
}
h1 = h1 * _1[i % 13];
h2 = h2 * _2[i % 17];
h2 ^= (h1 ^ 0x29aee) << 1;
h1 ^= (h2 ^ 0x29aee) << 1;
return (h1 ^ h2) & 0xffffff;
}
int main(){
scanf("%s%d", s, &Q);
memset(hmap, 0, sizeof hmap);
while(Q--){
scanf("%d%d", &l, &r);
--l;
t.assign(s + l, s + r);
pt = 0;
for(n = r - l, flag = false; ; flag = false){
st[pt] = getHcode(t);
// cout << "n = " << n << ", Str = " << t << ", hash = " << st[pt] << '\n';
if(hmap[st[pt]]){
puts(hmap[st[pt]] == 1 ? "No" : "Yes");
break; }
++pt;
for(i = 0; i < n - 1; i++)
if(t[i] == t[i + 1]){
if(t[i] == 'z'){
t.erase(i, 2);
n -= 2;
}else{
++t[i];
t.erase(i + 1, 1);
--n;
}
flag = true;
break;
}
if(!flag){
puts(n ? "No" : "Yes");
while(pt > 0) hmap[st[--pt]] = n ? 1 : 2;
break;
}
}
}
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Robot and String |
User |
vjudge1 |
Language |
Bash (GNU bash v4.3.11) |
Score |
0 |
Code Size |
1854 Byte |
Status |
RE |
Exec Time |
10 ms |
Memory |
652 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 1300 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt |
All |
0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt, 1_50.txt, 1_51.txt, 1_52.txt, 1_53.txt, 1_54.txt, 1_55.txt, 1_56.txt, 1_57.txt, 1_58.txt, 1_59.txt, 1_60.txt, 1_61.txt, 1_62.txt, 1_63.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
RE |
10 ms |
632 KB |
0_01.txt |
RE |
10 ms |
596 KB |
0_02.txt |
RE |
10 ms |
640 KB |
1_00.txt |
RE |
9 ms |
648 KB |
1_01.txt |
RE |
9 ms |
640 KB |
1_02.txt |
RE |
10 ms |
648 KB |
1_03.txt |
RE |
9 ms |
628 KB |
1_04.txt |
RE |
10 ms |
632 KB |
1_05.txt |
RE |
9 ms |
652 KB |
1_06.txt |
RE |
9 ms |
612 KB |
1_07.txt |
RE |
10 ms |
600 KB |
1_08.txt |
RE |
10 ms |
640 KB |
1_09.txt |
RE |
9 ms |
636 KB |
1_10.txt |
RE |
10 ms |
652 KB |
1_11.txt |
RE |
9 ms |
608 KB |
1_12.txt |
RE |
9 ms |
644 KB |
1_13.txt |
RE |
9 ms |
640 KB |
1_14.txt |
RE |
9 ms |
632 KB |
1_15.txt |
RE |
10 ms |
640 KB |
1_16.txt |
RE |
10 ms |
600 KB |
1_17.txt |
RE |
10 ms |
600 KB |
1_18.txt |
RE |
10 ms |
636 KB |
1_19.txt |
RE |
10 ms |
636 KB |
1_20.txt |
RE |
9 ms |
612 KB |
1_21.txt |
RE |
9 ms |
652 KB |
1_22.txt |
RE |
9 ms |
636 KB |
1_23.txt |
RE |
9 ms |
640 KB |
1_24.txt |
RE |
9 ms |
636 KB |
1_25.txt |
RE |
9 ms |
628 KB |
1_26.txt |
RE |
9 ms |
652 KB |
1_27.txt |
RE |
9 ms |
572 KB |
1_28.txt |
RE |
9 ms |
640 KB |
1_29.txt |
RE |
9 ms |
640 KB |
1_30.txt |
RE |
9 ms |
644 KB |
1_31.txt |
RE |
9 ms |
640 KB |
1_32.txt |
RE |
9 ms |
640 KB |
1_33.txt |
RE |
9 ms |
640 KB |
1_34.txt |
RE |
9 ms |
644 KB |
1_35.txt |
RE |
9 ms |
640 KB |
1_36.txt |
RE |
9 ms |
644 KB |
1_37.txt |
RE |
9 ms |
640 KB |
1_38.txt |
RE |
9 ms |
612 KB |
1_39.txt |
RE |
9 ms |
636 KB |
1_40.txt |
RE |
9 ms |
648 KB |
1_41.txt |
RE |
9 ms |
628 KB |
1_42.txt |
RE |
9 ms |
640 KB |
1_43.txt |
RE |
9 ms |
636 KB |
1_44.txt |
RE |
9 ms |
644 KB |
1_45.txt |
RE |
9 ms |
640 KB |
1_46.txt |
RE |
9 ms |
640 KB |
1_47.txt |
RE |
9 ms |
640 KB |
1_48.txt |
RE |
9 ms |
612 KB |
1_49.txt |
RE |
9 ms |
636 KB |
1_50.txt |
RE |
9 ms |
648 KB |
1_51.txt |
RE |
9 ms |
632 KB |
1_52.txt |
RE |
9 ms |
636 KB |
1_53.txt |
RE |
9 ms |
648 KB |
1_54.txt |
RE |
9 ms |
636 KB |
1_55.txt |
RE |
9 ms |
600 KB |
1_56.txt |
RE |
9 ms |
644 KB |
1_57.txt |
RE |
9 ms |
644 KB |
1_58.txt |
RE |
9 ms |
644 KB |
1_59.txt |
RE |
9 ms |
640 KB |
1_60.txt |
RE |
9 ms |
600 KB |
1_61.txt |
RE |
9 ms |
640 KB |
1_62.txt |
RE |
10 ms |
608 KB |
1_63.txt |
RE |
9 ms |
636 KB |