Cod sursa(job #1480640)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 2 septembrie 2015 22:42:22
Problema Congr Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream>
#include <assert.h>

const char IN [ ] = "congr.in" ;
const char OUT[ ] = "congr.out" ;
const int MAX_N = 300000;

using namespace std;

ifstream cin ( IN );
ofstream cout ( OUT );

int a [ ( MAX_N << 1 ) - 1 ];
int pos [ (MAX_N << 1 ) - 1 ];

int xor128 ( void )
{
    static int x = 123456789;
    static int y = 362436069;
    static int z = 521288629;
    static int w = 88675123;
    int t = x ^ ( x << 11 );
    x = y;
    y = z;
    z = w;
    return w = w ^ ( w >> 19 ) ^ ( t ^ ( t >> 8 ) );
}

int main ( void )
{
    cin.tie ( 0 );
    ios_base :: sync_with_stdio ( 0 );
    int n;
    long long s = 0LL;

    cin >> n;
    for ( register int i = 0; i < n; i ++ )
    {
        cin >> a [ i ];
        pos [ i ] = i;
        s += a [ i ];
    }
    for ( register int i = 1; i < n; i ++ )
    {
        cin >> a [ i + n - 1 ];
        pos [ i + n - 1 ] = i + n - 1;
    }
    cin.close ( );
    while ( s % n )
    {
        int toSwap = xor128 ( ) % n;
        int with = n + xor128 ( ) % ( n - 1 );

        s += a [ pos [ with ] ] - a [ pos [ toSwap ] ];
        swap ( pos [ with ], pos [ toSwap ] );
    }
    s = 0LL;
    for ( register int i = 0; i < n; i ++ )
    {
        s += a [ pos [ i ] ];
        cout << pos [ i ] + 1 << ' ';
    }
    assert ( ! ( s % n ) );
    cout.close ( );
    return 0;
}