Cod sursa(job #562481)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 23 martie 2011 09:52:04
Problema Congr Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>
#include <cstdlib>
#include <algorithm>
#include <ctime>

using namespace std;

ifstream in ("congr.in");
ofstream out ("congr.out");

const int N = 600005;

int n, sum, MOD, v[N];

bool f[N];

void read() {
    in >> n;
    MOD = n;
    for (int i = 1; i < 2 * n; ++ i) {
        in >> v[i];
        v[i] %= MOD;
    }
}

int mod(int x) {
    if (x > MOD)
        x -= MOD;
    if (x < 0)
        x += MOD;
    return x;
}

void init() {
    for (int i = 1; i <= n; ++ i) {
        f[i] = 1;
        sum = mod(sum + v[i]);
    }
}

int get_rand(int x) {
    int rez = rand() % (2 * n - 1);
    while (f[rez] != x)
        rez = rand() % (2 * n - 1);
    return rez;
}

void solve() {
    int i1, i2;
    srand(time(0));
    while (sum) {
        i1 = get_rand(1);
        i2 = get_rand(0);
        f[i1] = 0;
        f[i2] = 1;
        sum = mod(sum - v[i1] + v[i2]);
    }
    for (int i = 1; i < 2 * n; ++ i)
        if(f[i])
            out << i << ' ';
}


int main() {
    read();
    init();
    solve();
    return 0;
}