oj.uz

Submission #318661

# Submission time Handle Problem Language Result Execution time Memory
318661 2020-11-02T20:32:08 Z ant101 Vrtić (COCI18_vrtic) C++14
160 / 160
 1668 ms 37736 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 of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |    if (dec[i - 1] < cyc[i].size()) {

Subtask #1
16.0 / 16.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4332 KB Output is correct

Subtask #3
16.0 / 16.0

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

Subtask #4
16.0 / 16.0

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

Subtask #5
16.0 / 16.0

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

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2304 KB Output is correct
2 Correct 67 ms 3648 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3820 KB Output is correct
2 Correct 475 ms 13668 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3684 KB Output is correct
2 Correct 476 ms 13532 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 5224 KB Output is correct
2 Correct 1668 ms 37736 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 5220 KB Output is correct
2 Correct 1644 ms 37480 KB Output is correct