제출 #239073

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
239073		kartel	Vrtić (COCI18_vrtic)	C++14	32 / 160	11 ms	2816 KiB

vrtic

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
#define N +100500
#define M ll(1e9 + 7)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e9)
#define el '\n'
#define pii pair <int, int>
using namespace std;
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;

int cur = 1e9, bestfriend[N], surprize[N], i, l, r, n, ans[N], maybeans[N], nm[N], cntcycles;
bool mk[N], mrk[N];
vector <int> cycle[N];

void rec(int k)
{
    if (k > cntcycles)
    {
        int j = n;
        for (int i = 1; i <= cntcycles; i++)
        {
            int l = 0;
            int r = sz(cycle[nm[i]]) - 1;

            while (l <= r)
            {
                maybeans[cycle[nm[i]][r]] = surprize[j];
                j--;
                r--;
                if (l > r) break;
                maybeans[cycle[nm[i]][l]] = surprize[j];
                j--;
                l++;
            }
        }

        int maybecur = 0;

        for (int i = 1; i <= n; i++) maybecur = max(maybecur, abs(maybeans[i] - maybeans[bestfriend[i]]));

        if (maybecur < cur)
        {
            cur = maybecur;
            for (int i = 1; i <= n; i++) ans[i] = maybeans[i];
        }

        return;
    }
    for (int i = 1; i <= n; i++)
        if (!mk[i])
    {
        mk[i] = 1;
        nm[k] = i;
        rec(k + 1);
        mk[i] = 0;
    }
}

void findcycle(int v)
{
    if (mrk[v]) return;
    mrk[v] = 1;

    cycle[cntcycles].pb(v);

    findcycle(bestfriend[v]);
}

int main()
{
    srand(time(0));
    ios_base::sync_with_stdio(0);
    iostream::sync_with_stdio(0);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

//    in("input.txt");
//    out("output.txt");

    cin >> n;
    for (i = 1; i <= n; i++) cin >> bestfriend[i];
    for (i = 1; i <= n; i++) cin >> surprize[i];

    sort(surprize + 1, surprize + 1 + n);

    i = 1;
    while (i < n && bestfriend[i] == i + 1) i++;

    if (i >= n && bestfriend[n] == 1)
    {

        l = 1;
        r = n;
        i = n;

        while (l <= r)
        {
            ans[r] = surprize[i];
            r--;
            i--;
            if (l > r) break;
            ans[l] = surprize[i];
            i--;
            l++;
        }

        cur = 0;

        for (i = 1; i <= n; i++) cur = max(cur, abs(ans[i] - ans[bestfriend[i]]));

        cout << cur << el;

        for (i = 1; i <= n; i++) cout << ans[i] << " ";
    }
    else
    {
        for (i = 1; i <= n; i++)
        {
            if (mrk[i]) continue;

            cntcycles++;
            nm[cntcycles] = cntcycles;

            findcycle(i);
        }

        int j = n;

        for (int i = 1; i <= cntcycles; i++)
        {
            int l = 0;
            int r = sz(cycle[nm[i]]) - 1;

            while (l <= r)
            {
                maybeans[cycle[nm[i]][r]] = surprize[j];
                j--;
                r--;
                if (l > r) break;
                maybeans[cycle[nm[i]][l]] = surprize[j];
                j--;
                l++;
            }
        }

        int maybecur = 0;

        for (int i = 1; i <= n; i++) maybecur = max(maybecur, abs(maybeans[i] - maybeans[bestfriend[i]]));

        if (maybecur < cur)
        {
            cur = maybecur;
            for (int i = 1; i <= n; i++) ans[i] = maybeans[i];
        }

//        rec(1);

        cout << cur << el;
        for (i = 1; i <= n; i++) cout << ans[i] << " ";
    }
}

/*
8 8
...).).*
*....)..
.)*(..).
(*)((...
.)).)(..
.)(.)..(
...).(.*
M.......
*/
//
//110000
//1100

• Subtask 1: 16 / 16
• Subtask 2: 16 / 16
• Subtask 3: 0 / 16
• Subtask 4: 0 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 16
• Subtask 7: 0 / 16
• Subtask 8: 0 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16