oj.uz

Submission #239073

# Submission time Handle Problem Language Result Execution time Memory
239073 2020-06-14T10:02:49 Z kartel Vrtić (COCI18_vrtic) C++14
32 / 160
 11 ms 2816 KB 
#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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2688 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2688 KB jury has better answer

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2720 KB jury has better answer

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2688 KB jury has better answer

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2688 KB jury has better answer
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 2688 KB jury has better answer
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2816 KB jury has better answer
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2688 KB jury has better answer
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 2688 KB jury has better answer
2 Halted 0 ms 0 KB -