Cod sursa(job #466072)

Utilizator MariusMarius Stroe Marius Data 25 iunie 2010 22:57:07
Problema Congr Scor Ascuns
Compilator cpp Status done
Runda Marime 1.2 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;

const char iname[] = "congr.in";
const char oname[] = "congr.out";


int main(void) {
    ifstream in(iname);
    int n;
    vector <int> numbers, used;

    assert(in >> n);
    assert(1 <= n && n <= 300000);
    numbers.resize(2 * n - 1);
    for (size_t i = 0; i < numbers.size(); ++ i) {
        assert(in >> numbers[i]);
        assert(0 <= numbers[i] && numbers[i] < 1000000);
        numbers[i] %= n;
    }
    in.close();

    ofstream out(oname);

    int currentSum = 0;
    used.assign(2 * n - 1, 0);
    for (int i = 0, j; i < n; ++ i) {
        do j = rand() % (2 * n - 1); while (used[j]);
        used[j] = true;
        currentSum = (currentSum + numbers[j]) % n;
    }
    for (int j; currentSum != 0; ) {
        do j = rand() % (2 * n - 1); while (!used[j]);
        used[j] = false;
        currentSum = (currentSum - numbers[j]) % n;
        do j = rand() % (2 * n - 1); while (used[j]);
        used[j] = true;
        currentSum = (currentSum + numbers[j]) % n;
    }
    for (int i = 0; i < 2 * n - 1; ++ i) if (used[i])
        out << i + 1 << " ";
    
    out.close();
    return 0;
}