Submission #6495353


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 4059 Byte
Status TLE
Exec Time 2108 ms
Memory 10112 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 4
AC × 16
TLE × 18
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 3 ms 5760 KB
01-02.txt TLE 2103 ms 6272 KB
01-03.txt TLE 2103 ms 6272 KB
01-04.txt TLE 2103 ms 7680 KB
01-05.txt TLE 2103 ms 6016 KB
01-06.txt TLE 2104 ms 7808 KB
01-07.txt TLE 2103 ms 7424 KB
01-08.txt TLE 2103 ms 6912 KB
01-09.txt TLE 2103 ms 7680 KB
01-10.txt TLE 2103 ms 9856 KB
01-11.txt AC 54 ms 7808 KB
01-12.txt AC 38 ms 7040 KB
01-13.txt AC 52 ms 7552 KB
01-14.txt AC 44 ms 7424 KB
01-15.txt AC 71 ms 8448 KB
01-16.txt TLE 2103 ms 10112 KB
01-17.txt TLE 2103 ms 8064 KB
01-18.txt TLE 2104 ms 8064 KB
01-19.txt TLE 2108 ms 8064 KB
01-20.txt TLE 2103 ms 8064 KB
01-21.txt TLE 2104 ms 8064 KB
01-22.txt TLE 2104 ms 8064 KB
01-23.txt TLE 2103 ms 8064 KB
01-24.txt TLE 2104 ms 8064 KB
01-25.txt AC 106 ms 9728 KB
01-26.txt AC 104 ms 9728 KB
01-27.txt AC 100 ms 9344 KB
01-28.txt AC 79 ms 8832 KB
01-29.txt AC 79 ms 8832 KB
01-30.txt AC 103 ms 10112 KB
sample-01.txt AC 3 ms 5760 KB
sample-02.txt AC 3 ms 5760 KB
sample-03.txt AC 3 ms 5760 KB
sample-04.txt AC 3 ms 5760 KB