Cod sursa(job #1724859)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 4 iulie 2016 14:11:02
Problema Congr Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
//
//  main.cpp
//  congr
//
//  Created by Niculae Alexandru on 04/07/16.
//  Copyright © 2016 Niculae Alexandru. All rights reserved.
//

#include <cstdio>
#include <algorithm>
#include <ctime>
#include <vector>
#include <cstdlib>


using namespace std;

const int nmax = 3e5 + 10;

int n , i , sum;
int a[nmax<<1] , pos[nmax<<1];
vector < int > in , out;

void add(int x , int a)
{
    x += a;
    if (x >= n) x -= n;
    if (x < 0) x += n;
}

int trueRand(int lim)
{
    long long val = (rand() << 25LL) + (rand() << 20LL) + (rand() << 10LL) + (rand() ^ 7528529) + (rand() ^ 257982) + rand();
    val %= lim;
    if (val < 0) val += lim;
    return (int) val;
}

int getRand(int st, int dr)
{
    return st + trueRand(dr-st+1);
}

int main()
{
    freopen("congr.in","r",stdin);
    freopen("congr.out","w",stdout);
    
    scanf("%d", &n);
    
    for (i = 1; i <= 2 * n + 1; ++i)
    {
        scanf("%d", a + i);
        a[i] %= n;
        
        pos[a[i]] = i;
    }
    
    for (i = 1; i <= 2 * n + 1; ++i) pos[i] = i;
    random_shuffle(pos + 1 , pos + 2 * n + 2);
    
    srand(time(0));
    
    for (i = 1; i <= n; ++i)
        in.push_back(pos[i]);
    
    for (i = n + 1; i <= 2 * n + 1; ++i)
        out.push_back(pos[i]);
    
    for (auto it = in.begin(); it != in.end(); ++it) add(sum , *it);
    
    while (sum)
    {
        int pos1 = getRand(0 , n - 1);
        int pos2 = getRand(0 , n);
        
        swap(in[pos1] , out[pos2]);
        
        add(sum , a[in[pos1]]);
        add(sum , -a[out[pos2]]);
    }
    
    for (auto it = in.begin(); it != in.end(); ++it)
        printf("%d ", *it);
    
    return 0;
}