TLE-T-16 (BinCoin)

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
#ifdef  ONLINE_JUDGE
    #define eprintf(...) 42
#else
        #define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#endif
clock_t startTime;
double getCurrentTime()
{
    return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
int solve()
{
    int n, k;
    cin>>n>>k;
    int arr[k][n], pos[k][n+1], l[k][n+1], r[k][n+1], cpy[k][n];
    int parent[n+1] = { 0 };
    for(int i=0; i<k; i++)
    {
        for(int j=0; j<n; j++)
        {
            cin>>arr[i][j];
            cpy[i][j] = arr[i][j];
            pos[i][arr[i][j]] = j; l[i][arr[i][j]] = j; r[i][arr[i][j]] = j;
        }
    }
    uniform_int_distribution<int> rnd(1,n);
    set<int> skippie;
    int shuff[n+1];
    for(int i=1; i<=n; i++)
    {
        shuff[i] = i;
    }
    while((int)skippie.size()<n)
    {
        skippie.clear();
        for(int p=0; p<n; p++)
        {
            for(int i=1; i<=n; i++)
            {
                int swappie = rnd(gen);
                swap(shuff[i], shuff[swappie]);
            }
            for(int m=1; m<=n; m++)
            {
                int i = shuff[m];
                if(skippie.count(i))
                {
                    continue;
                }
                bool vrai = true;
                set<int> neigh;
                for(int j=0; (j<k) && vrai; j++)
                {
                    if(pos[j][i]==0 || pos[j][i]==n-1)
                    {
                        vrai = false;
                        continue;
                    }
                    if(neigh.empty())
                    {
                        neigh.insert(arr[j][pos[j][i]-1]); neigh.insert(arr[j][pos[j][i]+1]);
                    }
                    else
                    {
                        if((!neigh.count(arr[j][pos[j][i]-1]))||(!neigh.count(arr[j][pos[j][i]+1])))
                        {
                            vrai = false;
                        }
                    }
                }
                if(vrai)
                {
                    for(auto child : neigh)
                    {
                        skippie.insert(child);
                        parent[child] = i;
                    }
                    skippie.insert(i);
                    for(int f=0; f<k; f++)
                    {
                        for(auto child : neigh)
                        {
                            l[f][i] = min(l[f][i], l[f][child]);
                            r[f][i] = max(r[f][i], r[f][child]);
                        }
                        arr[f][l[f][i]] = i; arr[f][r[f][i]] = i;
                    }
                }
            }
        }
        for(int i=0; i<k; i++)
        {
            for(int j=0; j<n; j++)
            {
                arr[i][j] = cpy[i][j];
                pos[i][arr[i][j]] = j; l[i][arr[i][j]] = j; r[i][arr[i][j]] = j;
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        cout<<(parent[i]==0 ? -1 : parent[i])<<" ";
    }
    cout<<endl;
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    //cin>>t;
    startTime = clock();
    while(t--)
    {
        startTime = clock();
        solve();
    }
    eprintf("time = %.5lf\n", getCurrentTime());
    return 0;
}