То выдает 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)

Try this test:

2
abc
b
1
abc

Correct answer: 1 1

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();

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

create suffix links...

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!

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

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.

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?

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