Codeforces 19C. Deletion of Repeats

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5 + 5;
int s[maxn];
int sa[maxn],rk[maxn];
int height[maxn];
int t1[maxn],t2[maxn],c[maxn];
int best[20][maxn];
int a[maxn],b[maxn];
vector<int>vv[maxn];
void getsa(int *s,int n,int m){
    int *x=t1,*y=t2;
    rep(i,0,m) c[i]=0;
    rep(i,0,n) c[x[i]=s[i]]++;
    rep(i,1,m) c[i]+=c[i-1];
    dep(i,n-1,0) sa[--c[x[i]]]=i;
    for(int k=1;k<=n;k<<=1){
        int p=0;
        rep(i,n-k,n) y[p++]=i;
        rep(i,0,n) if(sa[i]>=k) y[p++]=sa[i]-k;
        rep(i,0,m) c[i]=0;
        rep(i,0,n) c[x[y[i]]]++;
        rep(i,1,m) c[i]+=c[i-1];
        dep(i,n-1,0) sa[--c[x[y[i]]]]=y[i];
        swap(x,y);
        p=1; x[sa[0]]=0;
        rep(i,1,n) x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
        if(p>=n) break; m=p;
    }
}
void getheight(int n){
    int k=0;
    rep(i,1,n+1) rk[sa[i]]=i;
    rep(i,0,n){
        if(k) k--;
        int j=sa[rk[i]-1];
        while(s[i+k]==s[j+k]) k++;
        height[rk[i]]=k;
    }
}
void RMQ(int n){
    int lg=(int)(log(n*1.0)/log(2.0));
    rep(i,1,n+1) best[0][i]=height[i];
    rep(i,1,lg+1) for(int j=1;j+(1<<i)-1<=n;j++)
        best[i][j]=min(best[i-1][j],best[i-1][j+(1<<i>>1)]); 
}
int lcp(int x,int y){
    x=rk[x]; y=rk[y];
    if(x>y) swap(x,y); x++;
    int lg=(int)(log(1.0*(y-x+1))/log(2.0));
    return min(best[lg][x],best[lg][y-(1<<lg)+1]);
} // 贴板子
struct node{ int l,r,len; }p[maxn*10]; // 十倍是因为题目的"保证重复不过十次"
int cmp(node a,node b){ return a.len<b.len||a.len==b.len&&a.l<b.l; } // 按题意sort
int solve(){
    int n,cnt(0),ans(0); sc(n); rep(i,0,n) sc(a[i]),b[i]=a[i];
    sort(b,b+n); int bn=unique(b,b+n)-b; rep(i,0,n){
        s[i]=lower_bound(b,b+bn,a[i])-b+1;
        vv[s[i]].push_back(i);
    } getsa(s,n+1,maxn); getheight(n); RMQ(n);
    rep(i,0,maxn) rep(j,0,vv[i].size()) rep(k,j+1,vv[i].size()){
        if(vv[i][k]-vv[i][j]>n-vv[i][k]) continue;
        if(vv[i][k]-vv[i][j]<=lcp(vv[i][j],vv[i][k]))
            p[cnt++]={vv[i][j],vv[i][k],vv[i][k]-vv[i][j]};
        // 只要算一下这一段是不是重复的就可以 改成hash也差不多
    } sort(p,p+cnt,cmp); rep(i,0,cnt) if(p[i].l>=ans) ans=p[i].r;
    pf("%d\n",n-ans); rep(i,ans,n) pf("%d ",a[i]); return 0;
}
int main(){
    /* int _; sc(_); while(_--) */ solve();
}

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5 + 5;
map<int,int>aaa;
vector<int>vv[maxn];
int a[maxn],q[maxn];
int solve(){
    int n,cnt(0),ans(0); sc(n); rep(i,0,n){
        sc(a[i]); if(!aaa.count(a[i])) aaa[a[i]]=++cnt;
        q[i]=aaa[a[i]]; vv[aaa[a[i]]].push_back(i);
    } rep(i,0,n) for(auto x:vv[q[i]]){
        if(x>=i) break; if(i-x>n-i||x<ans) continue;
        int ff(0); rep(j,0,i-x) if(a[i+j]!=a[x+j]){ ff++; break; }
        if(!ff){ ans=i; break; }
    } pf("%d\n",n-ans); rep(i,ans,n) pf("%d ",a[i]);
}
int main(){
    /* int _; sc(_); while(_--) */ solve();
}

#include<bits/stdc++.h>
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
int main(){
    cout<<100000<<'\n';
    rep(i,0,10) rep(j,0,10000) cout<<(j==9999?10001+i:j+1)<<'\n';
}