oj.uz

Submission #239318

# Submission time Handle Problem Language Result Execution time Memory
239318 2020-06-15T11:23:22 Z VEGAnn Vrtić (COCI18_vrtic) C++14
96 / 160
 2000 ms 136336 KB 
#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
#define i2 array<int,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;
typedef long long ll;
const int N = 160;
const ll OO = 1e18;
const int oo = 2e9;
const int md = int(1e9) + 7;
map<vector<int>, i2> ff[N];
vector<int> vls, vc, from[N];
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());

    vc.clear();

    for (int i = 0; i < sz(vls); i++)
        vc.PB(0);

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

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

        for (int it = 0; it < sz(vc); it++){
            if (mem_siz[vls[it]] == vc[it]) continue;

            vc[it]++;

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

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

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

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

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

            vc[it]--;
        }
    }

    vc.clear();

    for (int i = 0; i < sz(vls); i++)
        vc.PB(mem_siz[vls[i]]);

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

    int rt = n;

    while (rt > 0){
        int pr = ff[rt][vc][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();

        vc[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 8 ms 384 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 38 ms 2808 KB Output is correct
2 Correct 575 ms 25688 KB Output is correct

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 10848 KB Output is correct
2 Execution timed out 2095 ms 116396 KB Time limit exceeded

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 6136 KB Output is correct
2 Execution timed out 2101 ms 116596 KB Time limit exceeded

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 16000 KB Output is correct
2 Execution timed out 2094 ms 134232 KB Time limit exceeded

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 16036 KB Output is correct
2 Execution timed out 2100 ms 136336 KB Time limit exceeded