Cod sursa(job #562491)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 23 martie 2011 10:01:01
Problema Congr Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <cstdlib>
#include <ctime>

using namespace std;

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

const int N = 600005;

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

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

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)
        sum = mod(sum + v[i]);
}

void solve() {
    int i1, i2, aux;
    srand(time(0));
    while (sum) {
        i1 = 1 + rand() % n;
        i2 = n + 1 + rand() % (n - 1);
        sum = mod(sum - v[poz[i1]] + v[poz[i2]]);
        aux = poz[i1];
        poz[i1] = poz[i2];
        poz[i2] = aux;
    }
    for (int i = 1; i <= n; ++ i)
            out << poz[i] << ' ';
}


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