| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 107026 |
2019-04-21T13:32:29 Z |
gs14004 |
Vrtić (COCI18_vrtic) |
C++17 |
|
1126 ms |
36740 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 155;
int n, p[MAXN], a[MAXN];
int cost[MAXN][MAXN];
int cnt[MAXN], vis[MAXN], ans[MAXN], clen[MAXN];
vector<int> v;
int fun(vector<int> &w){
int ans = 0;
for(int i=0; i<v.size(); i++){
ans *= cnt[v[i]] + 1;
ans += w[i];
}
return ans;
}
int dp[5000000];
int nxt[5000000];
int f(int pos, vector<int> &w){
if(pos == n) return 0;
int h = fun(w);
if(~dp[h]) return dp[h];
int ret = 2e9;
for(int i=0; i<v.size(); i++){
if(w[i]){
w[i]--;
int cv = max(f(pos + v[i], w), cost[pos + 1][pos + v[i]]);
if(ret > cv){
ret = cv;
nxt[h] = i;
}
w[i]++;
}
}
return dp[h] = ret;
}
vector<int> trace(int pos, vector<int> &w){
if(pos == n) return vector<int>();
int h = fun(w);
w[nxt[h]]--;
vector<int> k = trace(pos + v[nxt[h]], w);
w[nxt[h]]++;
k.insert(k.begin(), v[nxt[h]]);
return k;
}
int main(){
cin >> n;
for(int i=1; i<=n; i++) cin >> p[i];
for(int i=1; i<=n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
for(int i=1; i<=n; i++){
for(int j=i; j<=n; j++){
cost[i][j] = (j - i <= 2 ? (a[j] - a[i]) : 0);
}
}
for(int i=n; i; i--){
for(int j=1; j<=n; j++){
cost[i][j] = max({cost[i+1][j], cost[i][j-1], cost[i][j]});
}
}
for(int i=1; i<=n; i++){
if(!vis[i]){
int xcnt = 0;
for(int j=i; !vis[j]; j=p[j]){
vis[j] = 1;
xcnt++;
}
cnt[xcnt]++;
for(int j=i; !clen[j]; j=p[j]){
clen[j] = xcnt;
}
}
}
vector<int> w;
for(int i=1; i<=n; i++){
if(cnt[i]){
v.push_back(i);
w.push_back(cnt[i]);
}
}
memset(dp, -1, sizeof(dp));
cout << f(0, w) << endl;
auto seq = trace(0, w);
int pos = 0;
for(auto &i : seq){
for(int j=1; j<=n; j++){
if(vis[j] && clen[j] == i){
vector<int> seq(a + pos + 1, a + pos + i + 1);
{
vector<int> ans;
if(seq.size() % 2 == 0){
for(int i=0; i<seq.size(); i+=2){
ans.push_back(seq[i]);
}
for(int i=0; i<seq.size(); i+=2){
ans.push_back(seq[seq.size()-1-i]);
}
}
else{
for(int i=0; i<seq.size(); i+=2){
ans.push_back(seq[i]);
}
for(int i=1; i<seq.size(); i+=2){
ans.push_back(seq[seq.size()-1-i]);
}
}
seq = ans;
}
for(int k=j; vis[k]; k=p[k]){
vis[k] = 0;
ans[k] = seq.back();
seq.pop_back();
}
pos += i;
break;
}
}
}
for(int i=1; i<=n; i++) printf("%d ", ans[i]);
}
Compilation message
vrtic.cpp: In function 'int fun(std::vector<int>&)':
vrtic.cpp:13:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<v.size(); i++){
~^~~~~~~~~
vrtic.cpp: In function 'int f(int, std::vector<int>&)':
vrtic.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<v.size(); i++){
~^~~~~~~~~
vrtic.cpp: In function 'int main()':
vrtic.cpp:98:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<seq.size(); i+=2){
~^~~~~~~~~~~
vrtic.cpp:101:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<seq.size(); i+=2){
~^~~~~~~~~~~
vrtic.cpp:106:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<seq.size(); i+=2){
~^~~~~~~~~~~
vrtic.cpp:109:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1; i<seq.size(); i+=2){
~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
20088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
20016 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
20044 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
19968 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
19968 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
20068 KB |
Output is correct |
| 2 |
Correct |
53 ms |
20856 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
20352 KB |
Output is correct |
| 2 |
Correct |
400 ms |
25316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
20096 KB |
Output is correct |
| 2 |
Correct |
315 ms |
25208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
20400 KB |
Output is correct |
| 2 |
Correct |
1126 ms |
36736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
20344 KB |
Output is correct |
| 2 |
Correct |
979 ms |
36740 KB |
Output is correct |
