| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 239907 |
2020-06-17T13:29:00 Z |
MrRobot_28 |
Vrtić (COCI18_vrtic) |
C++17 |
|
7 ms |
1024 KB |
#include <bits/stdc++.h>
using namespace std;
vector <vector <int> > cycle;
vector <vector <int> > g;
vector <int> cycle1;
vector <bool> used;
void dfs(int v)
{
used[v] = true;
cycle1.push_back(v);
for(int i = 0; i < g[v].size(); i++)
{
int to = g[v][i];
if(!used[to])
{
dfs(to);
}
}
}
bool cmp(vector <int> a, vector <int> b)
{
return a.size() < b.size();
}
signed main(){
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// cout.tie(NULL);
int n;
cin >> n;
g.resize(n);
used.resize(n);
vector <int> p(n), c(n);
for(int i = 0; i < n; i++)
{
cin >> p[i];
p[i]--;
g[i].push_back(p[i]);
g[p[i]].push_back(i);
}
for(int i = 0; i < n; i++)
{
cin >> c[i];
}
sort(c.begin(), c.end());
if(n <= 20)
{
for(int i = 0; i < n; i++)
{
if(!used[i])
{
dfs(i);
cycle.push_back(cycle1);
cycle1.clear();
}
}
sort(cycle.begin(), cycle.end(), cmp);
int m = cycle.size();
vector <vector <int> > dp(n, vector <int> ((1 << m), 1e9));
vector <vector <int> > pred(n, vector <int> ((1 << m), -1));
for(int i = 0; i < n; i++)
{
int j = i;
int ns = 0;
for(int it = 0; it < cycle.size(); it++)
{
while(i - j + 1 <= cycle[it].size())
{
if(j < i && j >= 0)
{
if(j == i - 1)
{
ns = max(ns, c[j + 1] - c[j]);
}
else
{
ns = max(ns, c[j + 2] - c[j]);
}
}
j--;
}
if(j < -1)
{
break;
}
int e = ns;
if(cycle[it].size() >1)
{
e = max(e, c[j + 2] - c[j + 1]);
}
for(int mask = 0; mask < (1 << m); mask++)
{
if(((1 << it) & mask) != 0)
{
if(j == -1)
{
if(mask - (1 << it) == 0 &&e < dp[i][mask])
{
dp[i][mask] = e;
pred[i][mask] = it;
}
}
else if(max(e, dp[j][mask - (1 << it)]) < dp[i][mask])
{
dp[i][mask] = max(e, dp[j][mask - (1 << it)]);
pred[i][mask] = it;
}
}
}
}
}
int mask = (1 << m) - 1;
int pr = pred[n - 1][mask];
int ind = n - 1;
vector <int> ans(n);
while(ind >= 0)
{
int left = 0;
int right = cycle[pr].size() - 1;
for(int i = ind; ind - i + 1 <= cycle[pr].size(); i--)
{
if(i % 2 == 0)
{
ans[cycle[pr][right]] = c[i];
right--;
}
else
{
ans[cycle[pr][left]] = c[i];
left++;
}
}
mask -= (1 << pr);
ind -= cycle[pr].size();
if(ind != -1)
{
pr = pred[ind][mask];
}
}
cout << dp[n - 1][(1 << m) - 1]<< "\n";
for(int i = 0; i < n; i++)
{
cout << ans[i] << " ";
}
return 0;
}
vector <int> ans(n);
int res = 0;
int iter1 = n - 1, iter2 = 0;
for(int i = c.size() - 1; i >= 0; i--)
{
if(i % 2 == 0)
{
ans[iter1] = c[i];
iter1--;
}
else
{
ans[iter2] = c[i];
iter2++;
}
}
for(int i= 0; i < n; i++)
{
res = max(res, abs(ans[i]- ans[(i + 1) % n]));
}
cout << res << "\n";
for(int i= 0; i < n; i++)
{
cout << ans[i] << " ";
}
return 0;
}
Compilation message
vrtic.cpp: In function 'void dfs(int)':
vrtic.cpp:12:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[v].size(); i++)
~~^~~~~~~~~~~~~
vrtic.cpp: In function 'int main()':
vrtic.cpp:65:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int it = 0; it < cycle.size(); it++)
~~~^~~~~~~~~~~~~~
vrtic.cpp:67:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i - j + 1 <= cycle[it].size())
~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
vrtic.cpp:120:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = ind; ind - i + 1 <= cycle[pr].size(); i--)
~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
256 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 |
7 ms |
1024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
256 KB |
the dissatisfaction value doesn't match with your answer |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
256 KB |
the dissatisfaction value doesn't match with your answer |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
the dissatisfaction value doesn't match with your answer |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
the dissatisfaction value doesn't match with your answer |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
the dissatisfaction value doesn't match with your answer |
| 2 |
Halted |
0 ms |
0 KB |
- |
