Submission #1343810

#TimeUsernameProblemLanguageResultExecution timeMemory
1343810kokorooCarnival (EGOI23_carnival)C++20
100 / 100
369 ms31848 KiB
#include<bits/stdc++.h>
//#include<atcoder/all>

using namespace std;
//using namespace atcoder;
#define rep(i,n) for(ll i=0; i<n; i++)
#define rrep(i,n) for(ll i=n-1; i>=0; i--)
#define print(a) cout<<a<<endl
typedef long long ll;
#define yn(flg) if(flg){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#define YN(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define so(a) sort(a.begin(),a.end())
#define mp make_pair
#define vi vector<int>
#define vl vector<ll>
#define vs vector<string>
#define pb push_back
#define a2i(a,s) (ll)(a-s)
#define i2a(s,a) (char)(s+a)
#define ssize(a) a.size()
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<pair<ll,ll>,ll> P3;
typedef pair<pair<ll,ll>,pair<ll,ll>> P4;

typedef pair<ll, ll> Pll;
typedef pair<ll,Pll> Plll;
typedef pair<Pii, int> Piii;
const ll INF = 1000000000000000000;

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;

}
using ull=unsigned long long;

ll n;

//vector<ll> k(1009,0);
//bool b=false;
//void saiki(ll pos,ll p){
//	if(p==n){
//		b=true;
//		return;
//	}
//	k[pos]=1;
//
//	for(ll i=0;i<g[pos].size();i++){
//		ll nx=g[pos][i];
//		if(k[nx]==1)continue;
//		saiki(nx,p+1);
//		if(b==true){
//			cout<<nx<<" ";
//			return;
//		}
//	}
//	k[pos]=0;
//	return;
//}

int main(){
//入力

	cin.tie(0);
	ios::sync_with_stdio(0);

	cin>>n;
	vector<vector<ll> > a(n,vector<ll>(n));
	vector<set<ll> > g(n);

	for(ll i=1;i<n;i++){
		for(ll j=0;j<i;j++){
			cin>>a[i][j];
			if(j<=(i-1)/2){
				g[i].insert(a[i][j]);
				g[a[i][j]].insert(i);
			}
		}
	}



	ll X=INF,Y=0;

	for(ll i=0;i<n;i++){
		if(X>g[i].size()){
			X=g[i].size();
			Y=i;
		}
	}

	vector<ll> v;
//判定
	v.push_back(Y);
	for(ll i=0;i<n-1;i++){
		ll nx=INF,ny=0;
		for(ll j:g[Y]){
			if(nx>g[j].size()){
				nx=g[j].size();
				ny=j;
			}
		}
		for(ll j=0;j<n;j++){
			g[j].erase(Y);
		}
		Y=ny;
		v.push_back(Y);
	}

//出力
	for(ll i=0;i<n;i++)cout<<v[i]<<" ";
	cout<<endl;


	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...