Hi. Any ideas what they put inside the test file to #3? 4 d cd bcd abcd 1 eabcde 1 2 Thanks, found a bug :) У меня этот тест проходит :(, но WA 3... Может кто-нибудь помочь с тестом? I have passed your test,but I still WA#3.Why? Read badwords with spaces, so: 'this is badword' not: this is badword :) changes nothing, still wrong answer Could be space trimming of right side or left side a problem... Hi. Any ideas what they put inside the test file to #3? If you have WA 13, try this test: 1 a 1 b....ba , where b repeated ~130000 times If you've got rte 27: m can be more than 10000 Why wa2? #include <bits/stdc++.h> #define all(a) a.begin(), a.end() #define vc vector using namespace std; vc<int> p; string s; int n; void calcSuffixArray() { p.resize(n); vc<int> c(n), pn(n), cn(n), k(max(256, n)); for (char ch : s) { k[ch]++; } partial_sum(k.begin(), k.begin() + 256, k.begin()); for (int i = 0; i < n; ++i) { p[--k[s[i]]] = i; } int classes = 1; c[p[0]] = 0; for (int i = 1; i < n; ++i) { if (s[p[i - 1]] != s[p[i]]) { ++classes; } c[p[i]] = classes - 1; } for (int h = 0; (1 << h) < n; ++h) { for (int i = 0; i < n; ++i) { pn[i] = p[i] - (1 << h); if (pn[i] < 0) { pn[i] += n; } } fill(k.begin(), k.begin() + classes, 0); for (int i = 0; i < n; ++i) { k[c[pn[i]]]++; } partial_sum(k.begin(), k.begin() + classes, k.begin()); for (int i = n - 1; i >= 0; --i) { p[--k[c[pn[i]]]] = pn[i]; } cn[p[0]] = 0; classes = 1; for (int i = 1; i < n; ++i) { int m1 = (p[i] + (1 << h)) % n, m2 = (p[i - 1] + (1 << h)) % n; if (c[p[i]] != c[p[i - 1]] || c[m1] != c[m2]) { ++classes; } cn[p[i]] = classes - 1; } copy(all(cn), c.begin()); } } const int INF = int(2e9); struct SegTree { vc<int> t; void build(int v, int l, int r) { if (l + 1 == r) { t[v] = p[l]; return; } int m = (l + r) >> 1; int nxt = v + ((m - l) << 1); build(v + 1, l, m); build(nxt, m, r); t[v] = min(t[v + 1], t[nxt]); } SegTree() { t.resize(2 * n); build(0, 0, n); } int getMin(int v, int l, int r, int ql, int qr) { if (ql <= l && r <= qr) { return t[v]; } int m = (l + r) >> 1; int nxt = v + ((m - l) << 1); int ans = INF; if (ql < m) { ans = min(ans, getMin(v + 1, l, m, ql, qr)); } if (m < qr) { ans = min(ans, getMin(nxt, m, r, ql, qr)); } return ans; } }; struct comp { string t; int pos; comp(string t) : t(move(t)), pos(0) {} bool operator ()(const int& a, const int& b) { if (b == -1) { return (pos + a < s.size() ? s[a + pos] < t[pos] : true); } else { return (pos + b < s.size() ? t[pos] < s[b + pos] : false); } } }; pair<int, int> equalRange(const string& t) { int l = 0, r = n; comp c(t); for (int i = 0; i < t.size() && l < r; ++i) { l = lower_bound(p.begin() + l, p.begin() + r, -1, c) - p.begin(); r = upper_bound(p.begin() + l, p.begin() + r, -1, c) - p.begin(); c.pos++; } return make_pair(l, r); } void solve() { int w; cin >> w; vc<string> words(w); cin.get(); for (string& i : words) { getline(cin, i); } int rows; cin >> rows; cin.get(); vc<int> sz(rows); for (int i = 0; i < rows; ++i) { string add; getline(cin, add); add.push_back((i == rows - 1 ? '\0' : '\n')); sz[i] = add.size(); s += add; } n = s.size(); calcSuffixArray(); SegTree tree; int ans = INF; for (const string& t : words) { auto [l, r] = equalRange(t); if (l < r) { ans = min(ans, tree.getMin(0, 0, n, l, r)); } } if (ans == INF) { cout << "Passed"; return; } for (int i = 0; i < rows; ++i) { if (sz[i] <= ans) { ans -= sz[i]; } else { cout << i + 1 << ' ' << ans + 1 << endl; return; } } cout << "WTF"; } int main() { solve(); return 0; } I can't think of a way to store goto and fail transitions of so many vertices and avoid MLE. please help. here's code: #include <stdio.h> #include <queue> using namespace std; short g[110000][256]; short f[110000]; short o[110000]; short n,m,newstate=0; queue<short>Q; int main(void){ short i,pos=0,q,r,u,v,ch,state; scanf("%hd",&n);getchar(); for(i=1;i<=n;++i){ r=0; ch=getchar(); state=0; ++r; ch+=128; while(g[state][ch]){ state=g[state][ch]; ch=getchar(); ++r; ch+=128; } while(ch!='\n'+128){ newstate=newstate+1; g[state][ch]=newstate; state=newstate; ch=getchar(); ++r; ch+=128; } o[state]=r-1; } for(i=0;i<256;++i){ if(q=g[0][i]){ f[q]=0; Q.push(q); } } while(!Q.empty()){ r=Q.front(); Q.pop(); for(i=0;i<256;++i){ u=g[r][i]; if(!(u==0&&r>0)){ Q.push(u); v=f[r]; while(g[v][i]==0&&v>0) v=f[v]; f[u]=g[v][i]; if(o[u]==0) o[u]=o[f[u]]; } } } scanf("%hd",&m);getchar(); for(i=1;i<=m;++i){ q=0;r=0; while((ch=getchar())!='\n'){ ch+=128; ++r; while(g[q][ch]==0&&q>0) q=f[q]; q=g[q][ch]; if(o[q]){ printf("%hd %hd",i,r-o[q]+1); return 0; } } } printf("Passed\n"); return 0; } you got pretty close, modified your solution to get AC. let me know if you need hints :) ikhomeriki@gmail.com Edited by author 21.09.2018 23:04 Some testcases contain empty strings, which is very nasty, and they should be read in combination with scanf and gets. I had scanf("%d\n", &N) initially, which skipped the empty lines afterwards, so my gets() calls where kind of useless. Secondly, here are some testcases: 2 bc abcd 1 abcx Should return 1 2 2 bc abcd 1 abcd Should return 1 1 Check my submissions and learn how evil the problem is! Really tired trying to AC with Aho-Corasick. I would switch to suffix array and if not succeed to suffix tree. I had a MLE 7 test - I split the tree into 3 parts And choose the best 3 answers Accepted 0.593 !!!! ------------------------- Enough for the division into 2 parts Edited by author 30.07.2011 10:18 sorry its late, but can you elaborate please ? I suppose he divided obscene words in three parts. Then did Aho - Corasick string matching algorithm for each of the parts separately. Edited by author 07.07.2017 21:05 The new time limit is 1.0 seconds (old - 0.5s). All submissions have been rejudged. The number of authors who has AC remain almost the same. What is real TL? In statements it is 0.5s, but in solutions rating there are solutions which passed with time bigger than 0.5s. For some tasks, they had a bigger time limit before, but after it changed, old solutions might have not been rejudged for whatever reasons. can somebody explain how the example shown has answer as 6 33 and not 6 44? are we not supposed to give the word position? 33 is number of symbol position in line)) Edited by author 26.07.2015 22:28 Edited by author 26.07.2015 22:28 why authors didn't rejudge??? some authors got accepted more than 0.5 sec.... i don't understand why? Edited by author 04.06.2014 19:39 WA 30. Can anyone help me? Or just give AC code? I have spent to much time on this problem. email: LegionN7@i.ua Update: Accepted. Edited by author 05.03.2014 18:52 TL for this problem is 0.5s but list of successful submissions contains times up to 2s. Initially, in one trie node i stored: Node child, sibling, sufLink; byte parSymb; short lEnd; This is 4 * 3 + 1 + 2 = 15 bytes per node, ML 28. Then I used static array of nodes(maximum number of nodes is 99991), memory consumption per node is the same(instead of Node reference we store int), ML 28. At the end, I stored child, sibling, sufLink and parSymb(we need 17 bits for each memory pointer and 8 bits for parent symbol, 17 * 3 + 8 = 59 bits in total) in one long, and lEnd in short, only 10 bytes per node, and got AC! I use Aho Corasick algorithm but get "Wrong answer 3". Why? Please give me test 3. Edited by author 23.11.2012 13:28 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[] args) throws IOException { Scanner sc = new Scanner(System.in); BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); int n = sc.nextInt(); String S[] = new String[n]; for (int i = 0; i < n; i++) { S[i] = sc.next(); } int m = sc.nextInt(); String[] S2 = new String[m]; for (int i = 0; i < m; i++) { S2[i] = bf.readLine(); } int count = 0, tempcont = 0; boolean isFineded = false; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { StringTokenizer st = new StringTokenizer(S2[i]); count -= tempcont; tempcont = 0; while (st.hasMoreTokens()) { tempcont++; String temp = st.nextToken(); if (isExits(temp, S[j])) { count++; isFineded = true; System.out.println(i + 1 + " " + count); } else { count++; } } } tempcont = 0; } if (isFineded == false) { System.out.println("Passed"); } } static boolean isExits(String src, String str) { boolean bol=false; if (str.length() > src.length()) { return false; } else if (str.equals(src)) { return true; } else { for (int i = 0; i <= src.length() - str.length(); i++) { if (str.equals(src.substring(i, i + str.length()))) { bol=true; } } return bol; } } } 2 sweet dream 3 swee t drea m Correct answer is Passed |
|