Cod sursa(job #1480645)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 2 septembrie 2015 22:47:46
Problema Congr Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <fstream>

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

using namespace std;

ofstream cout ( OUT );

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

char buffer [ BUFFSIZE ];
int ptr = BUFFSIZE;

inline char getChr ( )
{
    if ( ptr == BUFFSIZE )
    {
        fread ( buffer, 1, BUFFSIZE, stdin );
        ptr = 0;
    }
    return buffer [ ptr ++ ];
}

inline int readInt ( )
{
    char c;
    int q = 0;

    do
    {
        c = getChr ( );
    } while ( !isdigit ( c ) );
    do
    {
        q = ( q << 1 ) + ( q << 3 ) + ( c - '0' );
        c = getChr ( );
    } while ( isdigit ( c ) );
    return q;
}

inline 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 )
{
    freopen ( IN, "r", stdin );
    int n;
    long long s = 0LL;

    n = readInt ( );
    for ( register int i = 0; i < n; i ++ )
    {
        a [ i ] = readInt ( );
        pos [ i ] = i;
        s += a [ i ];
    }
    for ( register int i = 1; i < n; i ++ )
    {
        a [ i + n - 1 ] = readInt ( );
        pos [ i + n - 1 ] = i + n - 1;
    }
    fclose ( stdin );

    while ( s - s / n * n )
    {
        int toSwap = ( xor128 ( ) % n );
        int with = n + ( xor128 ( ) % ( n - 1 ) );

        s += a [ pos [ with ] ] - a [ pos [ toSwap ] ];
        swap ( pos [ with ], pos [ toSwap ] );
    }

    for ( register int i = 0; i < n; i ++ )
        cout << pos [ i ] + 1 << ' ';
    cout.close ( );
    return 0;
}