| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 244337 |
2020-07-03T16:25:56 Z |
Vimmer |
Vrtić (COCI18_vrtic) |
C++14 |
|
2000 ms |
148228 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 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];
map <int, int> f[160];
map <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;
for (register int i = sz(sizes) - 1; i >= 0; i--)
{
int st = sizes[i];
if (cur / mult[st] == kol[st]) {cur %= mult[st]; continue;}
cur %= mult[st];
int nml = ml + mult[st];
int 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] << " ";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
4352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
4200 KB |
Output is correct |
| 2 |
Correct |
355 ms |
24268 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
115 ms |
11256 KB |
Output is correct |
| 2 |
Execution timed out |
2090 ms |
117404 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
8312 KB |
Output is correct |
| 2 |
Execution timed out |
2084 ms |
118144 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
205 ms |
16508 KB |
Output is correct |
| 2 |
Execution timed out |
2101 ms |
141480 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
188 ms |
16632 KB |
Output is correct |
| 2 |
Execution timed out |
2088 ms |
148228 KB |
Time limit exceeded |
