Cod sursa(job #1716029)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 11 iunie 2016 20:44:47
Problema Congr Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.22 kb
#include <fstream>
#include <vector>
#include <cstdlib>
#include <ctime>

using namespace std;

class InputReader {
    public:
        InputReader() {}
        InputReader(const char *file_name) {
            input_file = fopen(file_name, "r");
            cursor = 0;
            fread(buffer, SIZE, 1, input_file);
        }
        inline InputReader &operator >>(int &n) {
            while(buffer[cursor] < '0' || buffer[cursor] > '9') {
                advance();
            }
            n = 0;
            while('0' <= buffer[cursor] && buffer[cursor] <= '9') {
                n = n * 10 + buffer[cursor] - '0';
                advance();
            }
            return *this;
        }
    private:
        FILE *input_file;
        static const int SIZE = 1 << 17;
        int cursor;
        char buffer[SIZE];
        inline void advance() {
            ++ cursor;
            if(cursor == SIZE) {
                cursor = 0;
                fread(buffer, SIZE, 1, input_file);
            }
        }
};

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

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

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

    InputReader 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 = inside.back();
        inside.pop_back();

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

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

        sum += v[val_o] - v[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;
}