Cod sursa(job #1716021)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 11 iunie 2016 20:40:46
Problema Congr Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>
#include <vector>
#include <cstdlib>
#include <ctime>

using namespace std;

const int PMAX = 300005;
int v[PMAX];

vector <int> inside;
vector <int> outside;

int main()
{
    srand(time(NULL));

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

    int p = 0;
    cin >> p;

    for (int i = 0; i < 2 * p - 1; ++ i) {
        cin >> v[i];
        v[i] %= p;
    }

    int sum = 0;
    for (int i = 0; i < p; ++ i) {
        inside.push_back(i);
        sum += v[i];

        if (sum >= p)
            sum -= p;
    }
    for (int i = p; i < 2 * p - 1; ++ i)
        outside.push_back(i);

    while (sum) {
        swap(inside[rand() % inside.size()], inside.back());
        int val_i = v[inside.back()];
        inside.pop_back();

        swap(outside[rand() % outside.size()], outside.back());
        int val_o = v[outside.back()];
        outside.pop_back();

        inside.push_back(val_o);
        outside.push_back(val_i);

        sum += val_o - val_i;
        if (sum >= p)
            sum -= p;
        else if (sum < 0)
            sum += p;
    }

    for (int i = 0; i < p; ++ i)
        cout << inside[i] + 1 << " \n"[i + 1 == p];

    cin.close();
    cout.close();
    return 0;
}