If you are storing hashes in a segtree and using some custom prime divider the values of the parent nodes can be less than the child nodes because the remainder "makes a round", so to subtract u have to add that round, I think this is what is actually happening in test 2. I cant understand my mistake for TLE14. My code var s,s1,s2: string; z2,z1,a,i,f,p,code: integer;z,n:int64; ch:char; begin readln(s); readln(npalindrome? 1 100000); for i:=1 to n do begin readln(s2); if s2[1]='p' then begin a:=13;z1:=0;z2:=0; while s2[a]<>' ' do inc(a); val(copy(s2,13,a-13),z1,code); val(copy(s2,a+1,length(s2)-1),z2,code); z:=z2-z1+1; if z2>length(s) then z2:=length(s); s1:=copy(s,z1,z);
f := 1; p:=1; while (p<=length(s1)div 2)and(f<>0) do if (s1[p] <> s1[length(s1)-p+1]) then begin writeln('No'); f := 0; end else p:=p+1;
if f = 1 then writeln('Yes'); end else begin a:=8;z1:=0; while s2[a]<>' ' do inc(a); Val(copy(s2,8,a-8),z1,code); ch:=s2[a+1]; delete(s,z1,1); insert(ch,s,z1);
end; end; end. hell why WA1? i wanna get my TLE package main import ( "bufio" "os" "strings" "strconv" ) func main() { in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) buffer, _ := in.ReadString('\n') str := []rune(strings.Trim(buffer, "\n")) buffer, _ = in.ReadString('\n') count, _ := strconv.ParseUint(strings.Trim(buffer, "\n"), 10, 0) for k := uint64(0); k < count; k++ { buffer, _ = in.ReadString('\n') flds := strings.Fields(buffer) if []rune(flds[0])[0] == 'c' { i, _ := strconv.Atoi(flds[1]) str[i-1] = []rune(flds[2])[0] } else { i, _ := strconv.ParseUint(flds[1], 10, 0) j, _ := strconv.ParseUint(flds[2], 10, 0) if isPali(i-1, j-1, str) { out.WriteString("Yes\n") } else { out.WriteString("No\n") } } } out.Flush() } func isPali(i, j uint64, str []rune) bool { for i < j { if str[i] != str[j] { return false } i++ j-- } return true } Edited by author 22.03.2017 08:19 Edited by author 22.03.2017 08:19 Hello admins, please add anti-hash tests for this task. How to solve it without hashes? Actually, u can write double-hashes and easy pass these anti-hash tests. idea...! Hint: A string is palindrome if (and only if) its "RIGHT to LEFT" hash and "LEFT to RIGHT" hash are the same. Also for "Change" queries you need to use some data structure, such as Fenwick Tree or Segment Tree. Edited by author 06.03.2015 14:26 Edited by author 06.03.2015 14:26 Can you give some tests? abcda 5 palindrome? 1 5 palindrome? 1 1 change 4 b palindrome? 1 5 palindrome? 2 4 Хотелось бы пример теста #pragma comment(linker, "/STACK:16777216") #include <iostream> using namespace std; char str[100001]; bool isPalind(int start, int finish) { int fin = finish-1;//(int)finish-48 - 1; bool answer = true; for (int k=start-1; k<fin; k++) { if (str[k] != str[fin]) { return false; } fin--; } return true; } int main() { char c1, c2; int pos=0, m, fin; cin >> str; scanf("%d\n", &m); for (int i=0; i<m; i++) { scanf("%*[^? ]%c%d ", &c1, &pos); if (c1 == ' ') { scanf("%c", &c2); str[pos-1] = c2; } if (c1 == '?') { scanf("%d", &fin); if(isPalind(pos, fin)) { printf("Yes\n"); } else { printf("No\n"); } } } return 0; } Edited by author 01.11.2013 00:11 Асимптотика же O(nm) у вас. Пример теста: ааа..ааа (10^5 штук), и 10^5 запросов: ? 1 100000 I cant understand my mistake for WA2. I tried it on my PC. Its work. Edited by author 19.10.2013 14:34 can you post your code? I cant understand my mistake for WA2. I tried it on my PC. Its work. Edited by author 19.10.2013 14:34 Edited by author 19.10.2013 16:29 Edited by author 19.10.2013 16:28 var s,s1,s2: string; i,f,n,m,k,l,p,j,code: longint; ch:char; begin readln(s); readln(n); for i:=1 to n do begin readln(s2); if s2[1]='p' then begin Val(s2[13],j,code); Val(s2[15],k,code); s1:=copy(s,j,k-j+1); f := 0; for p:= 1 to length(s1) div 2 do if s1[p] <> s1[length(s1)-p+1] then begin writeln('No'); f := 1; end; if f = 0 then writeln('Yes'); end else begin Val(s2[8],m,code); ch:=s2[10]; delete(s,m,1); insert(ch, s,m); end; end; end. Maybe multiple No's? But you will take TLE. Try this test: aacdeabcdeabcdeabcde 1 palindrome? 1 20 |
|