// Problem: P5184 [COCI 2009/2010 #2] PASIJANS
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5184
// Memory Limit: 125 MB
// Time Limit: 1500 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int N = 1005;
int n, ln[N], ar[N][N], nw[N], mx;
ull hu[N][N], pw[N];

ull gh(int i, int l, int r)
{
    return hu[i][r] - hu[i][l - 1] * pw[r - l + 1];
}

int lc(int i, int p, int j, int q)
{
    int a = ln[i] - p + 1, b = ln[j] - q + 1, lo = 0, hi = min(a, b);
    while (lo < hi)
    {
        int md = (lo + hi + 1) >> 1;
        if (gh(i, p, p + md - 1) == gh(j, q, q + md - 1))
            lo = md;
        else
            hi = md - 1;
    }
    return lo;
}

struct nd
{
    int id;
};
bool operator<(const nd x, const nd y)
{
    int i = x.id, j = y.id, p = nw[i], q = nw[j];
    int a = ln[i] - p + 1, b = ln[j] - q + 1;
    int t = lc(i, p, j, q);
    if (t < a && t < b)
        return ar[i][p + t] > ar[j][q + t];
    return a < b;
}

priority_queue<nd> pq;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> ln[i];
        mx = max(mx, ln[i]);
        for (int j = 1; j <= ln[i]; j++)
            cin >> ar[i][j];
        nw[i] = 1;
    }
    pw[0] = 1;
    const ull B = 146527u;
    for (int i = 1; i <= mx; i++)
        pw[i] = pw[i - 1] * B;
    for (int i = 1; i <= n; i++)
    {
        hu[i][0] = 0;
        for (int j = 1; j <= ln[i]; j++)
            hu[i][j] = hu[i][j - 1] * B + (ull)(ar[i][j] + 1007);
        pq.push({i});
    }
    while (!pq.empty())
    {
        nd u = pq.top();
        pq.pop();
        int i = u.id;
        cout << ar[i][nw[i]] << ' ';
        if (++nw[i] <= ln[i])
            pq.push(u);
    }
    return 0;
}

/*
  Tocno rjesenje zadatka Pasijans. Trebao bi dobiti sve bodove.
  Autor: Goran Zuzic
*/

#include <algorithm>
#include <functional>

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <set>
#include <vector>
#include <string>

using namespace std;

typedef long long llint;

const int MAXN = 1024;

int n;
int L[ MAXN ];
int A[ MAXN ][ MAXN ]; // 4 MB

int rnk[ MAXN ][ MAXN ][ 10 ]; // 40 MB

struct state {
    int x, poc;
    llint rr;

    state() {}
    state(int _x, int _poc, llint _rr) : x(_x), poc(_poc), rr(_rr) {}

    friend bool operator < (const state &A, const state &B) {
        return A.rr < B.rr;
    }
} V[ MAXN * MAXN ]; // 16MB

int v_cnt = 0;
int Poc[ MAXN ];

struct pq_cmpf {
    bool operator()(int a, int b) const {
        int poca = Poc[a];
        int pocb = Poc[b];

        for (int bit = 9; bit >= 0; --bit) {
            if (poca + (1 << bit) > L[a] || pocb + (1 << bit) > L[b])
                continue;

            if (rnk[a][poca][bit] != rnk[b][pocb][bit])
                return rnk[a][poca][bit] < rnk[b][pocb][bit];
            else {
                poca += (1 << bit);
                pocb += (1 << bit);
            }
        }

        if (L[a] - poca != L[b] - pocb)
            return L[a] - poca > L[b] - pocb;

        return a < b;
    }
};

set< int, pq_cmpf > pq;

int main(void) {
    int suma_svih = 0;
    scanf("%d", &n);

    for (int i = 0; i < n; ++i) {
        scanf("%d", L + i);
        suma_svih += L[i];

        for (int j = 0; j < L[i]; ++j)
            scanf("%d", A[i] + j);
    }

    for (int b = 0; (1 << b) <= 1000; ++b) {
        int len = 1 << b;
        int pola = len / 2;
        v_cnt = 0;

        for (int i = 0; i < n; ++i)
            for (int j = 0; j + len <= L[i]; ++j) {
                llint Val = 0;

                if (len == 1) {
                    Val = A[i][j];
                } else {
                    Val = rnk[i][j][b - 1] * 100000100LL + rnk[i][j + pola][b - 1];
                }

                V[ v_cnt++ ] = state(i, j, Val);
            }

        llint last = -1;
        int koji = -1;
        sort(V, V + v_cnt);

        for (int i = 0; i < v_cnt; ++i) {
            if (last != V[i].rr) {
                last = V[i].rr;
                ++koji;
            }

            rnk[ V[i].x ][ V[i].poc ][ b ] = koji;
        }
    }

    for (int i = 0; i < n; ++i) {
        Poc[i] = 0;
        pq.insert(i);
    }

    for (int cnt = 0; !pq.empty(); ++cnt) {
        int x = *pq.begin();
        pq.erase(pq.begin());
        printf("%d%c", A[x][Poc[x]], cnt + 1 < suma_svih ? ' ' : '\n');
        ++Poc[x];

        if (Poc[x] != L[x])
            pq.insert(x);
    }

    return (0 - 0);
}

0 条评论

目前还没有评论...