Submission #244343

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
244343	2020-07-03T16:33:08 Z	Vimmer	Vrtić (COCI18_vrtic)	C++14	128 / 160	934 ms	262148 KB

vrtic

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#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 F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 100101
#define M ll(1e9 + 7)
#define inf 1e9 + 1e9

using namespace std;
using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef short int si;
typedef pair <int, int> par;
typedef array <int, 2> a2;

//typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int a[160], b[160], kol[160], siz[160], cost[160][160], id, idr[160];

vector <int> koler[160], who[160];

vector <int> gr[160][160];

gp_hash_table <int, int> f[160];

gp_hash_table <int, pair <int, int> > from[160];

int mult[160];

vector <int> sizes;

int calc(int l, int r)
{
    int mx = 0;

    for (int i = l; i <= r; i += 2) {mx = i; gr[l][r].pb(b[i]);}

    if (mx != r) mx++;
      else mx--;

    for (int i = mx; i >= l; i -= 2) gr[l][r].pb(b[i]);

    int ans = 0;

    for (int i = 0; i < sz(gr[l][r]); i++) ans = max(ans, abs(gr[l][r][i] - gr[l][r][(i + 1) % sz(gr[l][r])]));

    return ans;
}

int main()
{
    //freopen("input.txt", "r", stdin); //freopen("output4.txt", "w", stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n;

    cin >> n;

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

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

    sort(b, b + n);

    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++) cost[i][j] = calc(i, j);

    memset(idr, -1, sizeof(idr));

    for (int i = 0; i < n; i++)
      if (idr[i] == -1)
      {
            idr[i] = id;

            int nxt = a[i];

            siz[id]++;

            who[id].pb(i);

            while (idr[nxt] == -1)
            {
                who[id].pb(nxt);

                idr[nxt] = id;

                nxt = a[nxt];

                siz[id]++;
            }

            kol[siz[id]]++;

            koler[siz[id]].pb(id);

            if (kol[siz[id]] == 1) sizes.pb(siz[id]);

            id++;
      }

    sort(sizes.begin(), sizes.end());

    mult[sizes[0]] = 1;

    int sm = kol[sizes[0]];

    for (int i = 1; i < sz(sizes); i++) {mult[sizes[i]] = mult[sizes[i - 1]] * (1 + kol[sizes[i - 1]]); sm += kol[sizes[i]] * mult[sizes[i]];}

    f[0][0] = 0;

    for (register int r = 0; r < n; r++)
        for (auto it : f[r])
        {
            int val = it.S;

            int ml = it.F, cur = it.F, st, nml, nval;

            for (register int i = sz(sizes) - 1; i >= 0; i--)
            {
                st = sizes[i];

                if (cur / mult[st] == kol[st]) {cur %= mult[st]; continue;}

                cur %= mult[st];

                nml = ml + mult[st];

                nval = max(val, cost[r][r + st - 1]);

                if (f[r + st].find(nml) == f[r + st].end() || f[r + st][nml] > nval) {f[r + st][nml] = nval; from[r + st][nml] = {r, ml};}
            }
        }

    cout << f[n][sm] << endl;

    int ans[n];

    int r = n;

    int ml = sm;

    while (r != 0)
    {
        int nxt = from[r][ml].F;

        int nx = from[r][ml].S;

        int st = r - nxt;

        int id = koler[st].back();

        koler[st].pop_back();

        for (int i = 0; i < sz(who[id]); i++) ans[who[id][i]] = gr[nxt][r - 1][i];

        r = nxt;

        ml = nx;
    }

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


}

Subtask #1
16.0 / 16.0

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

Subtask #2
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	4480 KB	Output is correct

Subtask #3
16.0 / 16.0

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

Subtask #4
16.0 / 16.0

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

Subtask #5
16.0 / 16.0

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

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	3584 KB	Output is correct
2	Correct	84 ms	18388 KB	Output is correct

Subtask #7
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	9464 KB	Output is correct
2	Correct	472 ms	96768 KB	Output is correct

Subtask #8
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	6904 KB	Output is correct
2	Correct	457 ms	96520 KB	Output is correct

Subtask #9
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	57 ms	13048 KB	Output is correct
2	Runtime error	934 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #10
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	54 ms	12664 KB	Output is correct
2	Runtime error	914 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)

Submission #244343

Compilation message