Cod sursa(job #490339)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 6 octombrie 2010 09:02:10
Problema Congr Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstring>
#include <ctime>
#include <bitset>
#include <deque>
#include <fstream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef bool int01;
typedef char cha08;
typedef short int int16;
typedef int int32;
typedef float rea32;
typedef long long int int64;
typedef double rea64;

const cha08 Input[] = "congr.in";
const cha08 Output[] = "congr.out";

const int32 Dim = 300001;
const int32 Inf = 1000000;

int01 f[Dim];
int32 P, S;
int32 a[2 * Dim], ind[Dim];

int32 main() {

    ifstream fin( Input );
    ofstream fout( Output );

    srand( time( 0 ) );

    int32 i, x, y, aux;

    fin >> P;
    for( i = 0; i < 2 * P; ++i )
        fin >> a[i];

    for( i = 0; i < P; ++i ) {

        do
            ind[i] = rand() % (2 * P - 1);
        while( f[ind[i]] == true );

        f[ind[i]] = true;
        S = (S + a[ind[i]]) % P;
    }

//    for( int32 i = 0; i < P; ++i )
//        fout << ind[i] << " -> " << a[ind[i]] << "\n";

    while( S ) {

        do {

            x = ind[aux = rand() % P];
            y = rand() % (2 * P - 1);
        }
        while( x == y || f[y] == true );

        f[x] = false;
        S -= a[x];

        while( S < 0 )
            S += P;

        ind[aux] = y;
        f[y] = true;
        S = (S + a[y]) % P;
    }

    for( i = 0; i < P; ++i )
        fout << a[ind[i]] << " ";

    fin.close();
    fout.close();

    return 0;
}