Pagini recente » Cod sursa (job #2750358) | Cod sursa (job #3149547) | Cod sursa (job #3292678) | Cod sursa (job #2940701) | Cod sursa (job #466065)
Cod sursa(job #466065)
Utilizator |
Marius 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;
}