oj.uz

Submission #143352

# Submission time Handle Problem Language Result Execution time Memory
143352 2019-08-13T18:11:26 Z KCSC Vrtić (COCI18_vrtic) C++14
160 / 160
 1875 ms 37628 KB 
#include <bits/stdc++.h>
using namespace std;

const int DIM = 155;
const int MAX = 10000005;
const int INF = 1000000005;

bool oki[DIM];
int cst[DIM][DIM], dp[MAX], val[DIM];
int ans[DIM], nxt[DIM], fth[MAX];

vector<int> mat[DIM][DIM];
vector<vector<int>> cyc[DIM];

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

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 >> val[i];
	for (int i = 1; i <= n; ++i) {
		if (oki[i])
			continue;
		vector<int> axc;
		for (int j = i; !oki[j]; j = nxt[j]) {
			axc.push_back(j);
			oki[j] = true;
		}
		cyc[axc.size()].push_back(axc);
	}
	sort(val + 1, val + n + 1);
	for (int i = 1; i <= n; ++i) {
		for (int j = i; j <= n; ++j) {
			for (int k = i; k <= j; k += 2)
				mat[i][j].push_back(val[k]);
			for (int k = j - (j - i + 1) % 2; k >= i; k -= 2)
				mat[i][j].push_back(val[k]);
			cst[i][j] = abs(mat[i][j].front() - mat[i][j].back());
			for (int k = 1; k <= j - i; ++k)
				cst[i][j] = max(cst[i][j], abs(mat[i][j][k] - mat[i][j][k - 1]));
		}
	}
	val[n] = 1;
	for (int i = n; i >= 1; --i) 
		val[i - 1] = val[i] * (cyc[i].size() + 1);
	vector<int> lst;
	for (int i = 1; i <= n; ++i)
		if (cyc[i].empty())
			val[i] = INF;
		else
			lst.push_back(i);
	for (int msk = 1; msk < val[0]; ++msk)
		dp[msk] = INF;
	for (int msk = 0; msk < val[0]; ++msk) {
		vector<int> dec = decrypt(msk, n);
		int st = 0;
		for (int i : lst)
			st += dec[i - 1] * i;
		for (int i : lst) {
			if (dec[i - 1] < cyc[i].size()) {
				if (dp[msk + val[i]] > max(dp[msk], cst[st + 1][st + i])) {
					dp[msk + val[i]] = max(dp[msk], cst[st + 1][st + i]);
					fth[msk + val[i]] = i;
				}
			}
		}
	}
	vector<int> dec(n, 0);
	for (int i = 1; i <= n; ++i)
		dec[i - 1] = cyc[i].size();
	for (int msk = val[0] - 1, en = n; msk; msk -= val[fth[msk]]) {
		int ln = fth[msk];
		--dec[ln - 1]; en -= ln;
		for (int i = 0; i < ln; ++i)
			ans[cyc[ln][dec[ln - 1]][i]] = mat[en + 1][en + ln][i];
	}
	cout << dp[val[0] - 1] << endl;
	for (int i = 1; i <= n; ++i)
		cout << ans[i] << " ";
	return 0;
}

Compilation message

vrtic.cpp: In function 'int main()':
vrtic.cpp:73:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (dec[i - 1] < cyc[i].size()) {

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1016 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4344 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1016 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2168 KB Output is correct
2 Correct 77 ms 3580 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3836 KB Output is correct
2 Correct 550 ms 13716 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3596 KB Output is correct
2 Correct 548 ms 13528 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 5208 KB Output is correct
2 Correct 1875 ms 37628 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 5240 KB Output is correct
2 Correct 1849 ms 37556 KB Output is correct