Submission #244341

#TimeUsernameProblemLanguageResultExecution timeMemory
244341VimmerVrtić (COCI18_vrtic)C++14
128 / 160
2095 ms105412 KiB
#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]; unordered_map <int, a2> f[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, 0}; for (register int r = 0; r < n; r++) for (auto it : f[r]) { int val = it.S[0]; 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][0] > nval) f[r + st][nml] = {nval, r}; } } cout << f[n][sm][0] << endl; int ans[n]; int r = n; int ml = sm; while (r != 0) { int nxt = f[r][ml][1]; 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 -= mult[st]; } for (int i = 0; i < n; i++) cout << ans[i] << " "; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...