Relocation Game

We need to sort the given array elements. In order to reduce the cost, we must do an "in place" sorting. Moreover, O(NlgN) sorting algorithms will not pass due to the large constraints.

Hence we must use a linear sorting algorithm to sort the elements. Counting sort is one of the sorting algorithms we can use here. Here is a link to a nice tutorial on this topic: GeeksForGeeks.

Please refer to the judge solution for the implementation detail.

#include <bits/stdc++.h>
using namespace std;

typedef long long vlong;
#define ABS(x) ((x)<0?-(x):(x))

#ifdef forthright48
     #define debug(args...) {dbg,args; cerr<<endl;}
#else
    #define debug(args...)  // Just strip off all debug tokens
#endif

struct debugger{
    template<typename T> debugger& operator , (const T& v){
        cerr<<v<<" ";
        return *this;
    }
} dbg;

///======================  TEMPLATE ENDS HERE  =====================///

#define MAXN 20000

vlong t, tc = 0;
vlong n, a, b, c;
vector <vlong> v[MAXN];

int main () {
    #ifdef forthright48
    freopen ( "input.txt", "r", stdin );
    //freopen ( "output.txt", "w", stdout );
    #endif // forthright48

    //fast_cin;

    scanf("%lld", &t);
    assert(t>=1 && t<=10000);

    tc = 0;

    while(tc<t) {
        tc++;

        scanf("%lld", &n);
        assert(n>=1 && n<=10000);

        scanf("%lld", &a);
        assert(a>=0 && a<n);

        scanf("%lld", &b);
        assert(b>=0 && b<=1000000000);

        scanf("%lld", &c);
        assert(c>=0 && c<=1000000000);


        for (vlong i=0; i<=n; i++) {
            v[i].clear();
        }

        for (vlong i=0; i<n; i++) {
            v[a].push_back(i);
            a = ( a*b + c ) % n;
        }

        vlong res = 0;
        for (vlong i=0, j=0; i<n; i++) {
            for (auto k: v[i]) {
                res += ABS(j-k);
                j++;
            }
        }

        for (vlong i=0; i<=n; i++) {
            v[i].clear();
        }

        printf("%lld\n", res);
    }


    return 0;
}