oj.uz

Submission #142631

# Submission time Handle Problem Language Result Execution time Memory
142631 2019-08-10T06:56:18 Z KCSC Vrtić (COCI18_vrtic) C++14
16 / 160
 75 ms 1268 KB 
#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) {
		if (!val[i])
			continue;
		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);
	for (int i = 1; i <= n; ++i)
		if (!tot[i])
			val[i] = 0;
	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

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

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB jury has better answer

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB jury has better answer

Subtask #3
16.0 / 16.0

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

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB jury has better answer

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB jury has better answer

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 504 KB jury has better answer
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 1016 KB jury has better answer
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 636 KB jury has better answer
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 1268 KB jury has better answer
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 1140 KB jury has better answer
2 Halted 0 ms 0 KB -