Cod sursa(job #562489)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 23 martie 2011 09:58:35
Problema Congr Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 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], poz[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)
        sum = mod(sum + v[i]);
    for (int i = 1; i <= n; ++ i)
        poz[i] = i;
}

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


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