Pagini recente » Cod sursa (job #1711363) | Cod sursa (job #2622783) | Cod sursa (job #2136422) | Cod sursa (job #3131786) | Cod sursa (job #757818)
Cod sursa(job #757818)
#include <ctime>
#include <cstdlib>
#include <fstream>
using namespace std;
int N, A[600002];
int s1[300002], s2[300002];
int freq[300002];
int main()
{
ifstream fin("congr.in");
ofstream fout("congr.out");
fin >> N;
for (int i = 1; i <= 2 * N - 1; ++i)
{
fin >> A[i];
A[i] %= N;
}
int sum = 0;
for (int i = 1; i <= N; ++i)
{
sum += A[i];
if (sum >= N) sum -= N;
s1[++s1[0]] = i;
}
for (int i = N + 1; i <= 2 * N - 1; ++i)
{
s2[++s2[0]] = i;
++freq[A[i]];
}
srand(time(0));
while (sum != 0)
{
int out = rand() % N + 1, in = rand() % (N - 1);
sum -= A[s1[out]];
if (sum < 0) sum += N;
if (freq[N - sum])
{
for (int i = 1; i <= s2[0]; ++i)
if (A[s2[i]] == N - sum)
{
sum = 0;
swap(s1[out], s2[i]);
break;
}
}
else
{
sum += A[s2[in]];
++freq[A[s1[out]]], --freq[A[s2[in]]];
swap(s1[out], s2[in]);
}
if (sum >= N) sum -= N;
}
for (int i = 1; i <= N; ++i)
fout << s1[i] << ' ';
fout << '\n';
fin.close();
fout.close();
}