Submission #1225692


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];

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;
		string t(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 1844 Byte
Status RE
Exec Time 9 ms
Memory 652 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1300
Status
RE × 3
RE × 67
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 9 ms 636 KB
0_01.txt RE 9 ms 644 KB
0_02.txt RE 9 ms 612 KB
1_00.txt RE 9 ms 608 KB
1_01.txt RE 9 ms 648 KB
1_02.txt RE 9 ms 640 KB
1_03.txt RE 9 ms 632 KB
1_04.txt RE 9 ms 640 KB
1_05.txt RE 9 ms 632 KB
1_06.txt RE 9 ms 636 KB
1_07.txt RE 9 ms 640 KB
1_08.txt RE 9 ms 636 KB
1_09.txt RE 9 ms 632 KB
1_10.txt RE 9 ms 636 KB
1_11.txt RE 9 ms 652 KB
1_12.txt RE 9 ms 612 KB
1_13.txt RE 9 ms 632 KB
1_14.txt RE 9 ms 636 KB
1_15.txt RE 9 ms 612 KB
1_16.txt RE 9 ms 612 KB
1_17.txt RE 9 ms 636 KB
1_18.txt RE 9 ms 644 KB
1_19.txt RE 9 ms 640 KB
1_20.txt RE 9 ms 636 KB
1_21.txt RE 9 ms 640 KB
1_22.txt RE 9 ms 572 KB
1_23.txt RE 9 ms 640 KB
1_24.txt RE 9 ms 640 KB
1_25.txt RE 9 ms 640 KB
1_26.txt RE 9 ms 636 KB
1_27.txt RE 9 ms 640 KB
1_28.txt RE 9 ms 644 KB
1_29.txt RE 9 ms 612 KB
1_30.txt RE 9 ms 632 KB
1_31.txt RE 9 ms 652 KB
1_32.txt RE 9 ms 612 KB
1_33.txt RE 9 ms 572 KB
1_34.txt RE 9 ms 640 KB
1_35.txt RE 9 ms 636 KB
1_36.txt RE 9 ms 648 KB
1_37.txt RE 9 ms 636 KB
1_38.txt RE 9 ms 572 KB
1_39.txt RE 9 ms 636 KB
1_40.txt RE 9 ms 612 KB
1_41.txt RE 9 ms 644 KB
1_42.txt RE 9 ms 640 KB
1_43.txt RE 9 ms 640 KB
1_44.txt RE 9 ms 636 KB
1_45.txt RE 9 ms 640 KB
1_46.txt RE 9 ms 612 KB
1_47.txt RE 9 ms 632 KB
1_48.txt RE 9 ms 636 KB
1_49.txt RE 9 ms 632 KB
1_50.txt RE 9 ms 632 KB
1_51.txt RE 9 ms 612 KB
1_52.txt RE 9 ms 640 KB
1_53.txt RE 9 ms 648 KB
1_54.txt RE 9 ms 648 KB
1_55.txt RE 9 ms 596 KB
1_56.txt RE 9 ms 636 KB
1_57.txt RE 9 ms 612 KB
1_58.txt RE 9 ms 644 KB
1_59.txt RE 9 ms 608 KB
1_60.txt RE 9 ms 640 KB
1_61.txt RE 9 ms 608 KB
1_62.txt RE 9 ms 640 KB
1_63.txt RE 9 ms 640 KB