Cod sursa(job #466065)

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

#define DEBUG 0

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

const int MAX_N = 2005;

bitset <MAX_N> dp[MAX_N], bk[MAX_N];

int modulo(int v, int p) {
    v %= p;
    if (v < 0) v += p;
    return v;
}

int main(void) {
    ifstream in(iname);
    int p, number, solution = false;
    vector < pair <int, int> > vect;

    in >> p;
    for (size_t i = 0; i < 2 * p - 1; ++ i) {
        in >> number;
        vect.push_back(make_pair(number % p, i));
    }
    in.close();

    ofstream out(oname);

    sort(vect.begin(), vect.end());
    for (int i = 0; i < p - 1 && !solution; ++ i) if (vect[p + i].first - vect[i].first == 0) {
        for (int j = i; j < p + i; ++ j)
            out << vect[j].second + 1 << "\n";
        solution = true;
if (DEBUG) {
        cerr << "1\n";
}
    }
    if (!solution) {
        int s = 0;
        for (int i = 0; i < p; ++ i)
            s = (s + vect[i].first) % p;
        if (s == 0) {
            for (int i = 0; i < p; ++ i)
                out << vect[i].second + 1 << "\n";
            solution = true;
if (DEBUG) {
            cerr << "2\n";
}
        }
        if (!solution) {
            dp[0][modulo(vect[p].first - vect[0].first, p)] = true;
            bk[0][modulo(vect[p].first - vect[0].first, p)] = true;
            for (int i = 1; i < p - 1; ++ i) {
                for (int j = 0; j < p; ++ j) {
                    if (dp[i - 1][j]) {
                        dp[i][j] = true;
                        bk[i][j] = false;
                    }
                    if (dp[i - 1][modulo(j - (vect[p + i].first - vect[i].first), p)]) {
                        dp[i][j] = true;
                        bk[i][j] = true;
                    }
                }
            }
if (DEBUG) { 
            cerr << s << "\n";
            for (int i = 0; i < p - 1; ++ i)
                cerr << modulo(vect[p + i].first - vect[i].first, p) << " ";  cerr << "\n";
            for (int i = 0; i < p - 1; ++ i) {
                cerr << i << ": ";
                for (int j = 0; j < p; ++ j)
                    cerr << dp[i][j] << " ";
                cerr << "\n";
            }
}
            vector <int> sol(2 * p - 1);
            for (int i = 0; i < p; ++ i)  sol[i] = 1;
            for (int i = p - 2, j = p - s; ; -- i ) {
                assert(dp[i][j] == true);
                if (bk[i][j] == true) {
                    j = modulo(j - vect[p + i].first + vect[i].first, p);
                    sol[i] = 0;
                    sol[p + i] = 1;
                }
                if (i == 0)  break;
            }
            for (int i = 0; i < 2 * p - 1; ++ i) if (sol[i])
                out << vect[i].second + 1 << "\n";
if (DEBUG) {
            cerr << "3\n";
}
        }
    }

    out.close();
    return 0;
}