Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | WA #3 :( | Rafal | 1269. Антимат | 15 мар 2024 14:29 | 8 | Hi. Any ideas what they put inside the test file to #3? У меня этот тест проходит :(, но 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 had trouble with 13/27 tests | Aleksey[TheCrawfish]Bykov'` | 1269. Антимат | 18 сен 2022 21:42 | 1 | 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 | WA2 suffix array | Dan | 1269. Антимат | 28 июн 2019 02:09 | 1 | 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; } | help with aho corasick MLE 7! | muhammad | 1269. Антимат | 21 сен 2018 23:02 | 2 | 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 | 8 test | Artem | 1269. Антимат | 11 авг 2018 00:25 | 1 | 8 test Artem 11 авг 2018 00:25 | Pitfalls | Gary Ye | 1269. Антимат | 14 сен 2017 20:39 | 2 | 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 | The problem is really evil. | Mahilewets | 1269. Антимат | 10 июл 2017 12:21 | 2 | 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 - Accepted 0.593 | uu_Innk | 1269. Антимат | 7 июл 2017 21:04 | 3 | 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 | Time limit update in problem 1269 Obscene Words Filter | Vladimir Yakovlev (USU) | 1269. Антимат | 26 июн 2016 22:33 | 1 | 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. | to admins | Vladimir Leskov`` | 1269. Антимат | 21 май 2016 21:31 | 2 | to admins Vladimir Leskov`` 21 май 2016 20:10 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. | test case answer | rakeshvarna | 1269. Антимат | 26 июл 2015 22:27 | 2 | 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 | To admins | Adhambek | 1269. Антимат | 26 июн 2015 19:00 | 1 | why authors didn't rejudge??? some authors got accepted more than 0.5 sec.... i don't understand why? | Do NOT forget to output the "Passed" - word in the end, for WA#5!!!! | Yerlan | 1269. Антимат | 29 дек 2014 17:14 | 1 | | WA1 | Kirill Luchikhin | 1269. Антимат | 4 июн 2014 19:30 | 1 | WA1 Kirill Luchikhin 4 июн 2014 19:30 Edited by author 04.06.2014 19:39 | WA 30 | Disintegrator | 1269. Антимат | 3 мар 2014 21:03 | 1 | WA 30 Disintegrator 3 мар 2014 21:03 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 | To admins: rejudge forgotten | Nike (Vologda ML) | 1269. Антимат | 23 май 2013 19:45 | 1 | TL for this problem is 0.5s but list of successful submissions contains times up to 2s. | A way to solve this problem in java | 2rf | 1269. Антимат | 6 мар 2013 01:10 | 1 | 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! | Test 3 | Alexander Goncharov | 1269. Антимат | 23 ноя 2012 13:28 | 1 | Test 3 Alexander Goncharov 23 ноя 2012 13:28 I use Aho Corasick algorithm but get "Wrong answer 3". Why? Please give me test 3. Edited by author 23.11.2012 13:28 | Crash Where is my mistake? | behzodbek | 1269. Антимат | 15 окт 2012 00:37 | 1 | 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; } } } | If you got WA15, try this test | standy | 1269. Антимат | 22 июл 2012 17:42 | 1 | 2 sweet dream 3 swee t drea m Correct answer is Passed |
|
|