Cod sursa(job #490351)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 6 octombrie 2010 09:36:11
Problema Congr Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 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 = 600001;

int01 f[Dim];
int32 P, S;
int32 a[Dim];

int32 main() {

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

    srand( time( 0 ) );

    int32 i, x, y;

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

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

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

        f[x] = true;
        S = S + a[x];
        while( S >= P )
            S -= P;
    }

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

    while( S ) {

        do {

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

        S = S + P - a[x] + a[y];
        while( S >= P )
            S -= P;
        f[x] = false;
        f[y] = true;
    }

    for( i = 0; i < 2 * P - 1; ++i )
        if( f[i] == true )
            fout << i + 1 << " ";

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

    return 0;
}