ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1269. Антимат

WA2 suffix array
Послано Dan 28 июн 2019 02:09
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;
}