Submission #6495857


Source Code Expand

Copy
#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

Submission Time
Task B - Do Not Duplicate
User Shibuyap
Language C++14 (GCC 5.4.1)
Score 0
Code Size 4089 Byte
Status TLE
Exec Time 2103 ms
Memory 5376 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 4
AC × 31
TLE × 3
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt
All 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt
Case Name Status Exec Time Memory
01-01.txt AC 2 ms 1024 KB
01-02.txt AC 16 ms 1792 KB
01-03.txt AC 19 ms 1792 KB
01-04.txt AC 53 ms 3712 KB
01-05.txt AC 14 ms 1536 KB
01-06.txt AC 66 ms 3840 KB
01-07.txt AC 64 ms 3456 KB
01-08.txt TLE 2103 ms 2176 KB
01-09.txt TLE 2103 ms 2944 KB
01-10.txt TLE 2103 ms 3200 KB
01-11.txt AC 51 ms 3200 KB
01-12.txt AC 35 ms 2304 KB
01-13.txt AC 49 ms 2816 KB
01-14.txt AC 45 ms 2688 KB
01-15.txt AC 71 ms 3840 KB
01-16.txt AC 66 ms 4096 KB
01-17.txt AC 60 ms 4096 KB
01-18.txt AC 67 ms 4096 KB
01-19.txt AC 78 ms 4096 KB
01-20.txt AC 77 ms 4096 KB
01-21.txt AC 73 ms 4204 KB
01-22.txt AC 84 ms 4096 KB
01-23.txt AC 90 ms 4096 KB
01-24.txt AC 87 ms 4096 KB
01-25.txt AC 102 ms 5120 KB
01-26.txt AC 100 ms 4992 KB
01-27.txt AC 96 ms 4736 KB
01-28.txt AC 78 ms 4096 KB
01-29.txt AC 77 ms 4096 KB
01-30.txt AC 102 ms 5376 KB
sample-01.txt AC 2 ms 1024 KB
sample-02.txt AC 2 ms 1024 KB
sample-03.txt AC 2 ms 1024 KB
sample-04.txt AC 2 ms 1024 KB