Submission #1348118

#TimeUsernameProblemLanguageResultExecution timeMemory
1348118settopCarnival (EGOI23_carnival)C++20
100 / 100
45 ms2428 KiB
#include<bits/stdc++.h>

using namespace std;

#define int long long
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define pb push_back
const int MAXN=2e3+10;

int n,grau[MAXN];
bool z[MAXN][MAXN],foi[MAXN];

int32_t main(){
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n;

    fall(i,1,n-1){
        fall(j,0,i-1){
            int x; cin>>x;
            if(j<=(i-1)/2) z[i][x]=z[x][i]=1,grau[i]++,grau[x]++;
        }
    }
    vector<int> ord(n); iota(all(ord),0);
    sort(all(ord),[&](int a,int b){
        if(grau[a]!=grau[b]) return grau[a]<grau[b];
        return a<b;
    });
    cout<<ord[0]<<" "; foi[ord[0]]=1;
    int last=ord[0];
    fall(_,1,n-1){
        ord.clear();
        fall(i,0,n-1) if(z[last][i]==1) grau[i]--;
        fall(i,0,n-1) if(!foi[i]) ord.pb(i);
        sort(all(ord),[&](int a,int b){
            if(grau[a]!=grau[b]) return grau[a]<grau[b];
            return a<b;
        }); 
        for(auto x:ord){
            if(z[last][x]){
                cout<<x<<" ";
                foi[x]=1;
                last=x;
                break;
            }
        }
    }   
    cout<<"\n";
}
#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...