Submission #6495857

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}

int main() {
    ll n,k;
    cin >> n >> k;

    int a[n];
    int ccc[200005] = {};
    rep(i,n){
        cin >> a[i];
        ccc[a[i]]++;
    }
    int count[200005];
    
    int next[n];
    int first[n];
    rep(i,n){
        next[i] = -1;
        first[i] = -1;
    }
    rep(i,200005)count[i] = -1;
    rep(i,n){
        if(count[a[i]] == -1){
            count[a[i]] = i;
            next[i] = i;
            first[a[i]] = i;
        }else{
            next[count[a[i]]] = i;
            count[a[i]] = i;
            next[i] = -999;
        }
    }

    rep(i,n){
        if(next[i]==-999){
            next[i] = first[a[i]];
        }
    }

    int head[200005][2];
    int tale[200005][2];
    rep(i,200005){
        rep(j,2){
            head[i][j] = -777;
            tale[i][j] = -777;
        }
    }

    int ddd[200005] = {};

    rep(i,n){
        if(ccc[a[i]]>=4){
            if(ddd[a[i]]==0){
                head[a[i]][0] = i;
            }else if(ddd[a[i]]==1){
                head[a[i]][1] = i;
            }else if(ddd[a[i]]==ccc[a[i]]-2){
                tale[a[i]][0] = i;
            }else if(ddd[a[i]]==ccc[a[i]]-1){
                tale[a[i]][1] = i;
            }
        }
        ddd[a[i]]++;
    }


    ll now = 0;

    while(true){
        ll tmp = now;
        int x = a[now%n];
        int fff = 0;
        /*
        if(now+n+100<n*k-1){
            if(ccc[x]>=4){
                if(now%n==head[x][0]){
                    if(ccc[x]%2==0){
                        now += tale[x][0]-head[x][0];
                    }else{
                        now += tale[x][1]-head[x][0];
                    }
                    now++;
                    fff = 1;
                }else if(now%n==head[x][1]){
                    if(ccc[x]%2==0){
                        now += tale[x][1]-head[x][1];
                    }else{
                        now += tale[x][0]-head[x][1];
                    }
                    now++;
                    fff = 1;
                }
            }
        }
        */
        if(fff==0){
            if(next[now%n]==now%n){
                now += n;
                now++;
            }else if(next[now%n]>now%n){
                now += (next[now%n]-now%n);
                now++;
            }else{
                now += (n+next[now%n]-now%n);
                now++;
            }
        }
        
        

        if(now>=n*k-1){
            now = tmp;
            break;
        }else{
            if(now%n==0){
                ll loop = now;
                now += (((n*k-1)-now)/loop)*loop;
            }
        }
    }

    int ans[n+100] = {};
    int c = 0;

    while(true){
        if(now == n*k)break;
        int x = a[now%n];
        if(next[now%n]==now%n){
            if(n*k-1<now+n){
                cout << x << ' ';
                now++;
            }else{
                now = now + n;
                now++;
            }
        }else if(next[now%n]>now%n){
            if(n*k-1<now + (next[now%n]-now%n)){
                cout << x << ' ';
                now++;
            }else{
                now += (next[now%n]-now%n);
                now++;
            }
        }else{
            if(n*k-1<now + (n+next[now%n]-now%n)){
                cout << x << ' ';
                now++;
            }else{
                now += (n+next[now%n]-now%n);
                now++;
            }
        }
    }

    
    cout << endl;
    return 0;
}
 
 

Submission Info

Judge Result