Page 5 То выдает Memory limit exceeded на 200 Кб, то Time limit exceeded на 46 или даже 15 мс. Как я понимаю, тут только имитация реальной проверки, и ожидается какое-то конкретное решение, а не нормально работающее. Кто прошёл эти круги ада, помогите советом! Моё решение использует алгоритм Ахо-Корасика, на тестовых данных выдаёт правильные результаты. Заменил HashMap в нодах на массив [256] - всё равно не проходит, те же ошибки. Я не знаю что думать, весь день убил на эту ерунду. Edited by author 14.02.2025 01:16 if MLE, avoid next[100001][256] and use a "flatmap" datastructure instead. (just store key-value pairs in dynamic array) 4 aceg ACEG {Ç}{Æ} {F}{E}{D} 3 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ ¡¢£¤¥¦§¨©ª«¬®¯°±²³´µ¶·¸¹º»¼½¾¿ÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏÐÑÒÓÔÕÖרÙÚÛÜÝÞßàáâãäåæçèéêëìíîïðñòóôõö÷øùúûüýþ {!}{"}{#}{$}{%}{&}{'}{(}{)}{*}{+}{,}{-}{.}{/}{0}{1}{2}{3}{4}{5}{6}{7}{8}{9}{:}{;}{<}{=}{>}{?}{@}{A}{B}{C}{D}{E}{F}{G}{H}{I}{J}{K}{L}{M}{N}{O}{P}{Q}{R}{S}{T}{U}{V}{W}{X}{Y}{Z}{[}{\}{]}{^}{_}{`}{a}{b}{c}{d}{e}{f}{g}{h}{i}{j}{k}{l}{m}{n}{o}{p}{q}{r}{s}{t}{u}{v}{w}{x}{y}{z}{{}{|}{}}{~}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{ }{¡}{¢}{£}{¤}{¥}{¦}{§}{¨}{©}{ª}{«}{¬}{}{®}{¯}{°}{±}{²}{³}{´}{µ}{¶}{·}{¸}{¹}{º}{»}{¼}{½}{¾}{¿}{À}{Á}{Â}{Ã}{Ä}{Å}{Æ}{Ç}{È}{É}{Ê}{Ë}{Ì}{Í}{Î}{Ï}{Ð}{Ñ}{Ò}{Ó}{Ô}{Õ}{Ö}{×}{Ø}{Ù}{Ú}{Û}{Ü}{Ý}{Þ}{ß}{à}{á}{â}{ã}{ä}{å}{æ}{ç}{è}{é}{ê}{ë}{ì}{í}{î}{ï}{ð}{ñ}{ò}{ó}{ô}{õ}{ö}{÷}{ø}{ù}{ú}{û}{ü}{ý}{þ} {þ}{ý}{ü}{û}{ú}{ù}{ø}{÷}{ö}{õ}{ô}{ó}{ò}{ñ}{ð}{ï}{î}{í}{ì}{ë}{ê}{é}{è}{ç}{æ}{å}{ä}{ã}{â}{á}{à}{ß}{Þ}{Ý}{Ü}{Û}{Ú}{Ù}{Ø}{×}{Ö}{Õ}{Ô}{Ó}{Ò}{Ñ}{Ð}{Ï}{Î}{Í}{Ì}{Ë}{Ê}{É}{È}{Ç}{Æ}{Å}{Ä}{Ã}{Â}{Á}{À}{¿}{¾}{½}{¼}{»}{º}{¹}{¸}{·}{¶}{µ}{´}{³}{²}{±}{°}{¯}{®}{}{¬}{«}{ª}{©}{¨}{§}{¦}{¥}{¤}{£}{¢}{¡}{ }{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{~}{}}{|}{{}{z}{y}{x}{w}{v}{u}{t}{s}{r}{q}{p}{o}{n}{m}{l}{k}{j}{i}{h}{g}{f}{e}{d}{c}{b}{a}{`}{_}{^}{]}{\}{[}{Z}{Y}{X}{W}{V}{U}{T}{S}{R}{Q}{P}{O}{N}{M}{L}{K}{J}{I}{H}{G}{F}{E}{D}{C}{B}{A}{@}{?}{>}{=}{<}{;}{:}{9}{8}{7}{6}{5}{4}{3}{2}{1}{0}{/}{.}{-}{,}{+}{*}{)}{(}{'}{&}{%}{$}{#}{"}{!} Passed or 3 166 In the statement, "any symbol" means NOT any valid ASCII char, but any byte, including those with codes 128..255. Common methods to read text in Rust, including stdin().read_line, expect valid UTF-8 and therefore crash on test 2 where bytes 128..255 are present. I got AC with this: let mut reader = BufReader::new(stdin()); let mut s = Vec::new(); reader.read_until(10, &mut s).unwrap(); 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; } Page 4 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. 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. 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 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 Pages: 5 4 3 2 1 Previous |
|