- 学术
SA
- 2025-8-19 1:57:19 @
// 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 条评论
目前还没有评论...