제출 #107026

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
107026		gs14004	Vrtić (COCI18_vrtic)	C++17	160 / 160	1126 ms	36740 KiB

vrtic

#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]);
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 16 / 16
• Subtask 8: 16 / 16
• Subtask 9: 16 / 16
• Subtask 10: 16 / 16