| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 239401 |
2020-06-15T13:30:11 Z |
VEGAnn |
Vrtić (COCI18_vrtic) |
C++14 |
|
1088 ms |
148932 KB |
#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 i2 array<int,2>
#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 *= (1ll + 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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
1024 KB |
Output is correct |
| 2 |
Correct |
49 ms |
7384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
3072 KB |
Output is correct |
| 2 |
Correct |
315 ms |
40460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
2048 KB |
Output is correct |
| 2 |
Correct |
304 ms |
40520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
4096 KB |
Output is correct |
| 2 |
Correct |
1081 ms |
148932 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
3968 KB |
Output is correct |
| 2 |
Correct |
1088 ms |
148932 KB |
Output is correct |
