HackerEarth Double Permutation problem solution

YASH PAL,
In this HackerEarth Double Permutation problem solution Ted has a random problem. This morning, he took two arrays consisting of permutations of the first N natural numbers and concatenated them together into a single array. But during his lunch break, his co-worker, Calvin, shuffled the numbers around!
To make matters worse, the numbers in the second of the two original permutations have grown into bigger numbers now. Each of them have increased by N. Afraid to look at what has become of his array, Ted first wants to know how many inversions he should expect in his array.
Luckily, Calvin is quite kind, and so he has given you a tip. He tells you the values of the permutation before some numbers have grown, but he doesn’t tell you which permutation each number was original from.
Since Ted doesn’t like real numbers with a lot of digits after the decimal point, he wants you to multiply the answer by 2N before printing it out. Ted understands that you might have difficulty dealing with such a large number now, so you should print it modulo 10^9+7.
HackerEarth Double Permutation problem solution

HackerEarth Double Permutation problem solution.

#include <iostream>
#include <cstdio>

using namespace std;

const int MOD=1000000007;
int N;
int A[200001];
int bit[100001];

void add(int x, int v)
{
    for(; x<=N/2; x+=x&-x)
        bit[x]+=v;
}

int sum(int x)
{
    int ret=0;
    for(; x>0; x-=x&-x)
        ret+=bit[x];
    return ret;
}

int main()
{
    scanf("%d", &N);
    long long p2=1;
    for(int i=2; i<N; i++)
        p2=(p2*2)%MOD;
    long long tmp=(((p2*N)%MOD)*(N==1?1:2))%MOD;
    long long ans=-7LL*N;
    N*=2;
    for(int i=1; i<=N; i++)
        scanf("%d", A+i);
    ans+=3LL*N*(N+1LL)/2LL;
    for(int i=1; i<=N; i++)
    {
        ans-=2*sum(A[i]);
        add(A[i], 1);
    }
    ans%=MOD;
    ans=(ans*p2)%MOD;
    ans=(ans+tmp)%MOD;
    printf("%lldn", ans);
    return 0;
}

Second solution

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

#define jjs(i, s, x) for (int i = (s); i < int(x); i++)
#define jjl(i, x) jjs(i, 0, x)
#define ji(x) jjl(i, x)
#define jj(x) jjl(j, x)
#define jk(x) jjl(k, x)
#define jij(a, b) ji(a) jj(b)
#define ever ;;
#define foreach(x, C) for (auto& x : (C))
#define INF ((int) 1e9+10)
#define LINF ((ll) 1e16)
#define pb push_back
#define mp make_pair
#define nrint(x) int x; rint(x);
#define nrlong(x) long long x; rint(x);
#define rfloat(x) scanf("%lf", &(x))

#ifndef ONLINE_JUDGE
const bool DEBUG = true;
#define Db(x...)   ({ if (DEBUG) { cout << "Debug["; DB, #x, ":", x, "]n"; } })
template<class T> void Dbrng(T lo, T hi, string note = "", int w = 0) {
  if (DEBUG) {  
    cout << "Debug[ ";
    if (!note.empty()) cout << setw(3) << note << " : ";
    for (; lo != hi; ++lo) cout << setw(w) << *lo << " ";
    cout << "]" << endl;
  }
}
struct Debugger { template<class T> Debugger& operator ,
  (const T & v) { cout << " " << v << flush; return *this; } } DB;
#else
const bool DEBUG = false;
#define Db(x...)
#endif

#define rint readInteger
template<typename T>
bool readInteger(T& x)
{
    char c,r=0,n=0;
    x=0;
    for (ever)
    {
        c=getchar();
        if ((c<0) && (!r))
            return(0);
        else if ((c=='-') && (!r))
            n=1;
        else if ((c>='0') && (c<='9'))
            x=x*10+c-'0',r=1;
        else if (r)
            break;
    }
    if (n)
        x=-x;
    return(1);
}

const int MOD = 1000000007;
typedef long long ll;
typedef pair<int, int> pi;

const int MX = 2e5;
const int OFFS = 3;
const int TMX = 1e5 + OFFS * 2;
int bit[TMX];

int bitRead(int x)
{
    x += OFFS;
    x = min(x, TMX - 1);
    int ans = 0;
    for (int i = x; i > 0; i -= i & -i)
        ans += bit[i];
    return ans;
}
void bitUpdate(int x, int v)
{
    x += OFFS;
    x = max(x, 1);
    for (int i = x; i < TMX; i += i & -i)
        bit[i] += v;
}

int N, arr[MX];
ll pow2[MX+1];
bool seen[MX];
int cnt[MX];
int base;

int main()
{
    rint(N);
    assert(1 <= N && N <= 100000);
    if (N == 1)
    {
        printf("1n");
        return 0;
    }
    base = N;
    N *= 2;
    ji(N) rint(arr[i]);
    ji(N) ++cnt[arr[i]];
    jjs(i, 1, base+1) assert(cnt[i] == 2);
    pow2[0] = 1;
    jjs(i, 1, MX+1) pow2[i] = pow2[i-1] * 2 % MOD;
    ll ans = 0;
    for (int i = N-1; i >= 0; i--)
    {
        ll lesser = bitRead(arr[i] - 1);
        ll greater = (N - i - 1) - lesser - seen[arr[i]];
        bitUpdate(arr[i], 1);
        seen[arr[i]] = true;
        ans += lesser * 3 % MOD * pow2[base - 2] % MOD;
        ans += greater          * pow2[base - 2] % MOD;
        ans %= MOD;
    }
    ans += base * pow2[base - 1] % MOD;
    ans %= MOD;
    printf("%lldn", ans);
}
coding problems solutions