Submission #142629

#	Time	Username	Problem	Language	Result	Execution time	Memory
142629		KCSC	Vrtić (COCI18_vrtic)	C++14	16 / 160	73 ms	1208 KiB

vrtic

#include <bits/stdc++.h>
using namespace std;

/*
#ifdef HOME
	const int DIM = ;
	const int INF = 1000000005;
	const int MXM = 50;
#else
*/
	const int DIM = 155;
	const int INF = 1000000005;
	const int MXM = 10000005;
//#endif

bool oki[DIM];
int nxt[DIM], cnt[DIM], val[DIM], dp[MXM], ans[DIM], fth[MXM];

vector<int> tot, aux;

vector<int> decrypt(int v, int n) {
	vector<int> msk(n + 1);
	for (int i = 1; i <= n; ++i) {
		while (v >= val[i]) {
			v -= val[i];
			++msk[i];
		}
	}
	return msk;
}

int encrypt(vector<int> &msk, int n) {
	int v = 0;
	for (int i = 1; i <= n; ++i) 
		for (int j = 1; j <= msk[i]; ++j)
			v += val[i];
	return v;
}

int main(void) {
#ifdef HOME	
	freopen("vrtic.in", "r", stdin);
	freopen("vrtic.out", "w", stdout);
#endif
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> nxt[i];
	for (int i = 1; i <= n; ++i)
		cin >> cnt[i];
	sort(cnt + 1, cnt + n + 1);	
	tot.resize(n + 1);
	for (int i = 1; i <= n; ++i) {
		if (oki[i])
			continue;
		int nr = 0;
		for (int j = i; ;) {
			if (oki[j])
				break;
			oki[j] = true;
			++nr; j = nxt[j];
		}
		++tot[nr];
	}
	val[n + 1] = 1;
	for (int i = n; i >= 1; --i) 
		val[i] = val[i + 1] * (tot[i + 1] + 1);
	int mxm = encrypt(tot, n);
	for (int i = 1; i <= mxm; ++i)
		dp[i] = INF;
	for (int v = 0; v < mxm; ++v) {
		aux = decrypt(v, n);
		int nr = 0;
		for (int i = 1; i <= n; ++i)
			nr += aux[i] * i;
		for (int i = 1; i <= n; ++i) {
			if (tot[i] == aux[i])
				continue;
			if (dp[v + val[i]] > max(dp[v], cnt[nr + i] - cnt[nr + 1])) {
				dp[v + val[i]] = max(dp[v], cnt[nr + i] - cnt[nr + 1]);
				fth[v + val[i]] = i;
			}
		}
	}
	for (int v = mxm, nr = n; v; v -= val[fth[v]]) {
		for (int i = 1; i <= n; ++i)
			oki[i] = false;
		for (int i = 1; i <= n; ++i) {
			if (oki[i] or ans[i])
				continue;
			vector<int> cyc;	
			for (int j = i; ;) {		
				if (oki[j])
					break;
				cyc.push_back(j);
				oki[j] = true; j = nxt[j];
			}
			if (cyc.size() == fth[v]) {
				for (int x : cyc) 
					ans[x] = cnt[nr--];
				break;
			}
		}
	}
	cout << dp[mxm] << endl;
	for (int i = 1; i <= n; ++i)
		cout << ans[i] << " ";			
	return 0;
}

Compilation message (stderr)

vrtic.cpp: In function 'int main()':
vrtic.cpp:98:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (cyc.size() == fth[v]) {
        ~~~~~~~~~~~^~~~~~~~~

• Subtask 1: 0 / 16
• Subtask 2: 0 / 16
• Subtask 3: 16 / 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