Cod sursa(job #467425)

Utilizator ProtomanAndrei Purice Protoman Data 28 iunie 2010 21:16:18
Problema Congr Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <algorithm>
#include <stdio.h>
#include <time.h>
#include <vector>

#define MAX 300010
#define pb push_back
#define mp make_pair
#define f first
#define s second

using namespace std;

int n, sum;
pair <int, int> x[MAX], v[MAX];
vector <int> pos[MAX];

int main()
{
    srand(time(0));
    freopen("congr.in", "r", stdin);
    freopen("congr.out", "w", stdout);

    scanf("%d", &n);

    for (int i = 1; i <= n; x[i].s = i, i++)
    {
        scanf("%d", &x[i].f);
        x[i].f %= n;

        sum = (sum + x[i].f) % n;
    }

    for (int i = 1; i < n; v[i].s = n + i, i++)
    {
        scanf("%d", &v[i].f);
        v[i].f %= n;

        pos[v[i].f].pb(i);
    }

    for (; sum % n; )
    {
        int out = rand() % n + 1;

        sum = (sum + n - x[out].f) % n;

        int in;
        if (pos[n - sum].size())
            in = pos[n - sum][pos[n - sum].size() - 1];
        else in = rand() % (n - 1) + 1;

        in = pos[v[in].f][pos[v[in].f].size() - 1];

        pos[x[out].f].pb(in);
        pos[v[in].f].pop_back();

        sum = (sum + v[in].f) % n;

        swap(x[out], v[in]);
    }

    for (int i = 1; i <= n; i++)
        printf("%d ", x[i].s);

    fclose(stdin);
    fclose(stdout);
    return 0;
}