Cod sursa(job #1735541)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 30 iulie 2016 08:29:49
Problema Congr Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;

const int PMAX = 300005;

class hpstream {
private:
    static const int BMAX = 1<<17;

    FILE *file;
    int   buff;
    char  str[BMAX];

    inline char nextch(void) {
        if(buff==BMAX) {
            fread(str, 1, BMAX, file);
            buff = 0;
        }
        return str[buff++];
    }

public:
    hpstream() {}
    hpstream(const char *str) {
        file = fopen(str, "r");
        buff = BMAX;
    }

    inline hpstream &operator>> (int &arg) {
        char ch, sgn=1;

        arg = 0;

        while(!isdigit(ch=nextch()) && ch!='-');

        if(ch=='-') {
            sgn=-1;
            ch=nextch();
        }
        arg=ch-'0';
        while(isdigit((ch=nextch())))
            arg=arg*10+ch-'0';

        arg*=sgn;

        return *this;
    }

    inline hpstream &operator>> (i64 &arg) {
        char ch, sgn=1;

        arg = 0;

        while(!isdigit(ch=nextch()) && ch!='-');

        if(ch=='-') {
            sgn=-1;
            ch=nextch();
        }
        arg=ch-'0';
        while(isdigit((ch=nextch())))
            arg=arg*10+ch-'0';

        arg*=sgn;

        return *this;
    }

    void close(void) {
        fclose(file);
    }
};

int   n, p, t;
i64         s;
vector<int> v, prm;

int main(void) {
    hpstream f("congr.in");
    ofstream g("congr.out");
    int pos1, pos2;

    srand(time(NULL));

    f>>p; n = 2 * p - 1;
    for(int i=0; i<n; ++i) {
        f>>t;
        v.push_back(t%p);
        prm.push_back(i);
    }

    random_shuffle(prm.begin(), prm.end());

    for(int i=0; i<p; ++i) {
        s+=v[prm[i]];
        if(s>=p)
            s-=p;
    }

    while(s) {
        pos1 = rand() % p;
        pos2 = rand() %(p - 1) + p;
        s   += v[prm[pos2]] - v[prm[pos1]];
        swap(prm[pos1], prm[pos2]);

        if(s>=p)
            s-=p;
        if(s<0)
            s+=p;
    }

    for(int i=0; i<p; ++i)
        g<<prm[i]+1<<' ';
    g<<'\n';

    f.close();
    g.close();
    return 0;
}