oj.uz

Submission #47375

# Submission time Handle Problem Language Result Execution time Memory
47375 2018-05-01T20:15:49 Z Bruteforceman Vrtić (COCI18_vrtic) C++11
96 / 160
 2000 ms 61844 KB 
#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

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.0 / 16.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
16.0 / 16.0

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

Subtask #5
16.0 / 16.0

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

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 2984 KB Output is correct
2 Correct 774 ms 26028 KB Output is correct

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 26028 KB Output is correct
2 Execution timed out 2067 ms 60744 KB Time limit exceeded

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 60744 KB Output is correct
2 Execution timed out 2065 ms 61844 KB Time limit exceeded

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 61844 KB Output is correct
2 Execution timed out 2057 ms 61844 KB Time limit exceeded

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 61844 KB Output is correct
2 Execution timed out 2064 ms 61844 KB Time limit exceeded