Submission #47375

#	Time	Username	Problem	Language	Result	Execution time	Memory
47375		Bruteforceman	Vrtić (COCI18_vrtic)	C++11	96 / 160	2067 ms	61844 KiB

vrtic

#include "bits/stdc++.h"
using namespace std;
int a[155];
int c[155];
int n;
typedef pair <int, int> pii;
int ans[155][155];
bool vis[155];
vector <int> v[155];
vector <int> cyc[155];

vector <int> sizes;

map <vector <int>, int> DP[155];
const int inf = 1000000000 + 7;
int cost[155];

int dp(int cur, vector <int> occ) {
	if(cur == n + 1) return 0;
	if(DP[cur].find(occ) != DP[cur].end()) return DP[cur][occ];
	int res = inf;
	for(size_t i = 0; i < sizes.size(); i++) {
		if(occ[i] > 0 && cur + sizes[i] - 1 <= n) {
			--occ[i];
			res = min(res, max(ans[cur][cur + sizes[i] - 1], dp(cur + sizes[i], occ)));
			++occ[i];
		}
	}
	return DP[cur][occ] = res;
}

int main(int argc, char const *argv[])
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	for(int i = 1; i <= n; i++) {
		scanf("%d", &c[i]);
	}
	sort(c + 1, c + n + 1);
	for(int i = 1; i <= n; i++) {
		for(int j = i; j <= n; j++) {
			ans[i][j] = 0;
			for(int k = i; k <= j-2; k++) {
				ans[i][j] = max(ans[i][j], c[k + 2] - c[k]);
			}
			if(i == j-1) {
				ans[i][j] = max(ans[i][j], c[j] - c[i]);
			}
		}
	}
	int idx = 0;
	map <int, int> cnt;
	for(int i = 1; i <= n; i++) {
		if(vis[i] == true) continue;
		int cur = i;
		++idx;
		while(vis[cur] == false) {
			vis[cur] = true;
			v[idx].push_back(cur);
			cur = a[cur];
		}
		int sz = v[idx].size();
		cyc[sz].push_back(idx);
		cnt[sz] += 1;
	}
	vector <int> occ;
	for(auto i : cnt) {
		sizes.push_back(i.first);
		occ.push_back(i.second);
	}	
	printf("%d\n", dp(1, occ));

	int cur = 1;

	while(cur <= n) {
		int res = dp(cur, occ);
		int opt = 0;
		for(size_t i = 0; i < sizes.size(); i++) {
			if(occ[i] > 0 && cur + sizes[i] - 1 <= n) {
				occ[i] -= 1;
				if(res == max(ans[cur][cur + sizes[i] - 1], dp(cur + sizes[i], occ))) {
					opt = i;
					break;
				}
				occ[i] += 1;
			}
		}
		int cycle = cyc[sizes[opt]].back();
		cyc[sizes[opt]].pop_back();

		int ptr = 0;
		for(int i = 0; i < sizes[opt]; i++) {
			if(i & 1) {
				cost[v[cycle][ptr++]] = c[cur + i];
			}
		}
		for(int i = sizes[opt] - 1; i >= 0; i--) {
			if(~i & 1) {
				cost[v[cycle][ptr++]] = c[cur + i];
			}
		}
		cur += sizes[opt];
	}
	for(int i = 1; i <= n; i++) {
		printf("%d ", cost[i]);
	}
	printf("\n");
	return 0;
}

Compilation message (stderr)

vrtic.cpp: In function 'int main(int, const char**)':
vrtic.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
vrtic.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
vrtic.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &c[i]);
   ~~~~~^~~~~~~~~~~~~

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