@OceanEye7年前
08/8
11:12
4278: [ONTAK2015]Tasowanie
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 434 Solved: 203
[Submit][Status][Discuss]
Description
给定两个数字串A和B，通过将A和B进行二路归并得到一个新的数字串T，请找到字典序最小的T。
Input
第一行包含一个正整数n(1<=n<=200000)，表示A串的长度。
第二行包含n个正整数，其中第i个数表示A[i](1<=A[i]<=1000)。
第三行包含一个正整数m(1<=m<=200000)，表示B串的长度。
第四行包含m个正整数，其中第i个数表示B[i](1<=B[i]<=1000)。
Output
输出一行，包含n+m个正整数，即字典序最小的T串。
Sample Input
6
1 2 3 1 2 4
7
1 2 2 1 3 4 3
1 2 3 1 2 4
7
1 2 2 1 3 4 3
Sample Output
1 1 2 2 1 2 3 1 2 3 4 3 4
HINT
Source
把两个串前后拼在一起 然后用SA处理出rank数组跑归并
中间插一个大大的分隔符就好
听说有姿势奇怪的贪心？【难道是某种神奇的哈希……】
现在不是很想理……
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
#include <cstdio> #include <algorithm> #include <cstring> #include <iostream> #include <cstdlib> #include <cmath> #define ll long long #define INF 1000000000 #define For(i,a,b) for(int i=a;i<=b;++i) #define p(x) ('0'<=x&&x<='9') char cc; int C; template <class T> void read( T &x ) { x=0; C=1; cc=getchar(); while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } #undef p using namespace std; #define N 200010 int Arr[N<<1],set[N<<1],n; int a[N<<1]; int SA[N<<1],rk[N<<1]; int buc[N<<1],fir[N<<1],sec[N<<1],tmp[N<<1]; void make_SA() { copy(Arr+1,Arr+1+n,set+1); sort(set+1,set+1+n); For(i,1,n) a[i]=lower_bound(set+1,set+1+n,Arr[i])-set; fill(buc,buc+1+n,0); For(i,1,n) buc[a[i]]++; For(i,1,n) buc[i]+=buc[i-1]; For(i,1,n) rk[i]=buc[a[i]-1]+1; bool unique; for(int p=1;p<=n;p<<=1) { For(i,1,n) fir[i]=rk[i],sec[i]=i+p>n?0:rk[i+p]; fill(buc,buc+1+n,0); For(i,1,n) buc[sec[i]]++; For(i,1,n) buc[i]+=buc[i-1]; For(i,1,n) tmp[n- --buc[sec[i]]]=i; fill(buc,buc+1+n,0); For(i,1,n) buc[fir[i]]++; For(i,1,n) buc[i]+=buc[i-1]; for(int j=1,i;j<=n;++j) { i=tmp[j]; SA[buc[fir[i]]--]=i; } unique=true; for(int j=1,i,last=0;j<=n;++j) { i=SA[j]; if(!last) rk[i]=1; else if(fir[last]==fir[i]&&sec[last]==sec[i]) unique=false,rk[i]=rk[last]; else rk[i]=rk[last]+1; last=i; } if(unique) break; } } int _,__; void init() { read(_); n=_; For(i,1,n) read(Arr[i]); Arr[++n]=2000; read(__); For(i,1,__) read(Arr[i+n]); n+=__; Arr[++n]=2000; } int main() { init(); make_SA(); int node1=1,node2=_+2; for(int i=1;i<n-1;i++) { printf("%d ",Arr[rk[node1]<rk[node2]?node1++:node2++]); } return 0; } |