oj.uz

Submission #239404

# Submission time Handle Problem Language Result Execution time Memory
239404 2020-06-15T13:32:27 Z VEGAnn Vrtić (COCI18_vrtic) C++14
160 / 160
 1103 ms 148896 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define i2 array<short,2>
#define PB push_back
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define ft first
#define sd second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
const int N = 160;
const ll OO = 1e18;
const int oo = 2e9;
const int md = int(1e9) + 7;
gp_hash_table<int, i2> ff[N];
vector<int> vls, from[N];
vector<int> muls;
int n, nt[N], a[N], ans[N], cnt, siz[N];
int comp[N], res[N], mem[N][N], mem_siz[N];

int get(int lf, int rt){
    ans[0] = a[lf];

    int fi = 0, se = 0, it = 1, mx = rt - lf;

    while (it + lf < rt){
        if (it & 1){
            fi++;

            if (fi == mx) fi -= mx;

            if (fi == se) break;

            ans[fi] = a[lf + it];
        } else {
            se--;

            if (se < 0) se += mx;

            if (fi == se) break;

            ans[se] = a[lf + it];
        }

        it++;
    }

    int sum = 0;

    for (int i = 0; i < mx; i++)
        sum = max(sum, abs(ans[i] - ans[(i + 1) % mx]));

    return sum;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> nt[i];
        nt[i]--;
    }

    for (int i = 0; i < n; i++)
        cin >> a[i];

    sort(a, a + n);

    fill(comp, comp + n, -1);

    for (int i = 0; i < n; i++){
        if (comp[i] >= 0) continue;

        comp[i] = cnt;
        siz[cnt] = 1;

        int loc = nt[i];

        while (comp[loc] < 0){
            comp[loc] = cnt;
            siz[cnt]++;
            loc = nt[loc];
        }

        mem_siz[siz[cnt]]++;
        vls.PB(siz[cnt]);
        from[siz[cnt]].PB(i);

        cnt++;
    }

    for (int lf = 0; lf < n; lf++)
    for (int rt = lf + 1; rt <= n; rt++)
        mem[lf][rt] = get(lf, rt);

    sort(all(vls));
    vls.resize(unique(all(vls)) - vls.begin());

    ll lst = 1;

    for (int i = 0; i < sz(vls); i++){
        if (i > 0)
            lst *= (1 + mem_siz[vls[i - 1]]);

        muls.PB(lst);
    }

    ff[0][0] = {0, 0};

    for (int i = 0; i < n; i++)
    for (auto state : ff[i]){
        ll cur = state.ft;
        i2 f = state.sd;
        ll memo = cur;

        for (int it = sz(vls) - 1; it >= 0; it--){
            int cur_cnt = cur / muls[it];

            cur -= cur_cnt * muls[it];

            if (cur_cnt == mem_siz[vls[it]]) continue;

            memo += muls[it];

            i2 nf = f;
            int rt = i + vls[it];

            nf[0] = max(nf[0], (short)mem[i][rt]);
            nf[1] = it;

            if (ff[rt].find(memo) == ff[rt].end()){
                ff[rt][memo] = nf;
                memo -= muls[it];
                continue;
            }

            i2& up = ff[rt][memo];

            if (up[0] > nf[0])
                up = nf;

            memo -= muls[it];
        }
    }

    lst = 0;

    for (int i = 0; i < sz(vls); i++)
        lst += ll(mem_siz[vls[i]]) * muls[i];

    cout << ff[n][lst][0] << '\n';

    int rt = n;

    while (rt > 0){
        int pr = ff[rt][lst][1];

        int lf = rt - vls[pr];

        get(lf, rt);

        for (int it = 0, loc = from[vls[pr]].back(); it < vls[pr]; it++){
            res[loc] = ans[it];
            loc = nt[loc];
        }

        from[vls[pr]].pop_back();

        lst -= muls[pr];
        rt = lf;
    }

    for (int i = 0; i < n; i++)
        cout << res[i] << " ";

    return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 512 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1024 KB Output is correct
2 Correct 50 ms 7488 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3072 KB Output is correct
2 Correct 304 ms 40476 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2048 KB Output is correct
2 Correct 319 ms 40460 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 4088 KB Output is correct
2 Correct 1079 ms 148816 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 3968 KB Output is correct
2 Correct 1103 ms 148896 KB Output is correct