| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 244328 |
2020-07-03T15:55:27 Z |
Vimmer |
Vrtić (COCI18_vrtic) |
C++14 |
|
20 ms |
8832 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];
unordered_map <ll, int> f[160];
unordered_map <ll, pair <int, ll> > from[160];
ll 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;
ll 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;
cout << f[n][sm] << endl;
int ans[n];
int r = n;
ll ml = sm;
while (r != 0)
{
int nxt = from[r][ml].F;
ll 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 |
Incorrect |
5 ms |
1152 KB |
the dissatisfaction value doesn't match with your answer |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
4480 KB |
the dissatisfaction value doesn't match with your answer |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
1824 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
1792 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
1792 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
3968 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
15 ms |
6400 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
15 ms |
6516 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
20 ms |
8832 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
8704 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
