oj.uz

답안 #107026

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
107026 2019-04-21T13:32:29 Z gs14004 Vrtić (COCI18_vrtic) C++17
160 / 160
 1126 ms 36740 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 155;

int n, p[MAXN], a[MAXN];
int cost[MAXN][MAXN];
int cnt[MAXN], vis[MAXN], ans[MAXN], clen[MAXN];

vector<int> v;

int fun(vector<int> &w){
	int ans = 0;
	for(int i=0; i<v.size(); i++){
		ans *= cnt[v[i]] + 1;
		ans += w[i];
	}
	return ans;
}

int dp[5000000];
int nxt[5000000];

int f(int pos, vector<int> &w){
	if(pos == n) return 0;
	int h = fun(w);
	if(~dp[h]) return dp[h];
	int ret = 2e9;
	for(int i=0; i<v.size(); i++){
		if(w[i]){
			w[i]--;
			int cv = max(f(pos + v[i], w), cost[pos + 1][pos + v[i]]);
			if(ret > cv){
				ret = cv;
				nxt[h] = i;
			}
			w[i]++;
		}
	}
	return dp[h] = ret;
}

vector<int> trace(int pos, vector<int> &w){
	if(pos == n) return vector<int>();
	int h = fun(w);
	w[nxt[h]]--;
	vector<int> k = trace(pos + v[nxt[h]], w);
	w[nxt[h]]++;
	k.insert(k.begin(), v[nxt[h]]);
	return k;
}

int main(){
	cin >> n;
	for(int i=1; i<=n; i++) cin >> p[i];
	for(int i=1; i<=n; i++) cin >> a[i];
	sort(a + 1, a + n + 1);
	for(int i=1; i<=n; i++){
		for(int j=i; j<=n; j++){
			cost[i][j] = (j - i <= 2 ? (a[j] - a[i]) : 0);
		}
	}
	for(int i=n; i; i--){
		for(int j=1; j<=n; j++){
			cost[i][j] = max({cost[i+1][j], cost[i][j-1], cost[i][j]});
		}
	}
	for(int i=1; i<=n; i++){
		if(!vis[i]){
			int xcnt = 0;
			for(int j=i; !vis[j]; j=p[j]){
				vis[j] = 1;
				xcnt++;
			}
			cnt[xcnt]++;
			for(int j=i; !clen[j]; j=p[j]){
				clen[j] = xcnt;
			}
		}
	}
	vector<int> w;
	for(int i=1; i<=n; i++){
		if(cnt[i]){
			v.push_back(i);
			w.push_back(cnt[i]);
		}
	}
	memset(dp, -1, sizeof(dp));
	cout << f(0, w) << endl;
	auto seq = trace(0, w);
	int pos = 0;
	for(auto &i : seq){
		for(int j=1; j<=n; j++){
			if(vis[j] && clen[j] == i){
				vector<int> seq(a + pos + 1, a + pos + i + 1);
				{
					vector<int> ans;
					if(seq.size() % 2 == 0){
						for(int i=0; i<seq.size(); i+=2){
							ans.push_back(seq[i]);
						}
						for(int i=0; i<seq.size(); i+=2){
							ans.push_back(seq[seq.size()-1-i]);
						}
					}
					else{
						for(int i=0; i<seq.size(); i+=2){
							ans.push_back(seq[i]);
						}
						for(int i=1; i<seq.size(); i+=2){
							ans.push_back(seq[seq.size()-1-i]);
						}
					}
					seq = ans;
				}
				for(int k=j; vis[k]; k=p[k]){
					vis[k] = 0;
					ans[k] = seq.back();
					seq.pop_back();
				}
				pos += i;
				break;
			}
		}
	}
	for(int i=1; i<=n; i++) printf("%d ", ans[i]);
}

Compilation message

vrtic.cpp: In function 'int fun(std::vector<int>&)':
vrtic.cpp:13:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~
vrtic.cpp: In function 'int f(int, std::vector<int>&)':
vrtic.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~
vrtic.cpp: In function 'int main()':
vrtic.cpp:98:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0; i<seq.size(); i+=2){
                    ~^~~~~~~~~~~
vrtic.cpp:101:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0; i<seq.size(); i+=2){
                    ~^~~~~~~~~~~
vrtic.cpp:106:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0; i<seq.size(); i+=2){
                    ~^~~~~~~~~~~
vrtic.cpp:109:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=1; i<seq.size(); i+=2){
                    ~^~~~~~~~~~~

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 20088 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 20016 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 20044 KB Output is correct

Subtask #4
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 19968 KB Output is correct

Subtask #5
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 19968 KB Output is correct

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 20068 KB Output is correct
2 Correct 53 ms 20856 KB Output is correct

Subtask #7
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 20352 KB Output is correct
2 Correct 400 ms 25316 KB Output is correct

Subtask #8
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 20096 KB Output is correct
2 Correct 315 ms 25208 KB Output is correct

Subtask #9
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 20400 KB Output is correct
2 Correct 1126 ms 36736 KB Output is correct

Subtask #10
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 20344 KB Output is correct
2 Correct 979 ms 36740 KB Output is correct