Submission #239896

#	Time	Username	Problem	Language	Result	Execution time	Memory
239896		MrRobot_28	Vrtić (COCI18_vrtic)	C++17	32 / 160	7 ms	1024 KiB

vrtic

#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;
				}
				for(int mask = 0; mask < (1 << m); mask++)
				{
					if(((1 << it) & mask) != 0)
					{
						if(j == -1)
						{
							if(mask - (1 << it) == 0 && max(ns, c[j + 2] - c[j + 1]) < dp[i][mask])
							{
								dp[i][mask] = max(ns, c[j + 2] - c[j + 1]);
								pred[i][mask] = it;
							}
						}
						else if(max(max(ns, c[j + 2] - c[j + 1]), dp[j][mask - (1 << it)]) < dp[i][mask])
						{
							dp[i][mask] = max(max(ns, c[j + 2] - c[j + 1]), 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];
			}
		}
		int res = 0;
		for(int i = 0; i < n; i++)
		{
			res = max(res, abs(ans[i] - ans[p[i]]));
		}
		cout << res << "\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 (stderr)

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:115:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = ind; ind - i + 1 <= cycle[pr].size(); i--)
                     ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 16 / 16
• Subtask 3: 0 / 16
• Subtask 4: 0 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 16
• Subtask 7: 0 / 16
• Subtask 8: 0 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16