제출 #1354524

#제출 시각아이디문제언어결과실행 시간메모리
1354524sallyCarnival (EGOI23_carnival)C++20
100 / 100
22 ms1448 KiB
#include<iostream>
#include<vector>
#include<cstring>
#include<deque>
#include<bits/stdc++.h>
#define rep(i, x) for(int i=0; i<x; i++)
using namespace std;
const int mx = 1005;
bool ok[mx][mx];
vector<int> cnt(mx, 0);
vector<vector<int>> g(mx);
vector<bool> vis(mx, false), used(mx, false);
bool got = false;
vector<int> ans;
int N;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>N;
    memset(ok, true, sizeof(ok));
    ok[0][0] = false;
    for(int i=1; i<N; i++) {
        ok[i][i] = false;
        for(int j=i; j>=1; j--) {
            int c;
            cin>>c;
            if(j<=i/2) {
                ok[i][c] = false;
                ok[c][i] = false;
            }
        }
    }
    // rep(i, N) {
    //     rep(j, N) {
    //         cout<<ok[i][j]<<' ';
    //     }
    //     cout<<'\n';
    // }
    int first, fc = 10000000;
    rep(i, N) {
        rep(j, N) {
            if(ok[i][j]) cnt[i]++;
        }
        if(cnt[i]<fc) {
                fc = cnt[i];
                first = i;
            }
    }   
    // rep(i, N) cout<<cnt[i]<<' ';
    // cout<<'\n';
    ans.push_back(first);
    used[first] = true;

    for(int k=2; k<=N; k++) {
        int t = ans.back();
        int f = 1000, ffc = 1000000;
        rep(j, N) {
            if(!ok[t][j] || used[j]) continue;
            if(ffc>cnt[j]) {
                ffc = cnt[j];
                f = j;
            }
        }    
        rep(i, N) {
            if(ok[t][i]) {
                cnt[i]--;
                ok[t][i] = ok[i][t] = false;
            }
        }
        // rep(j, N) {
        //     if(ok[f][j]) {
        //         cnt[j]--;
        //         ok[f][j] = ok[j][f] = false;
        //     }
        // }
        used[f] = true;
        ans.push_back(f);
    }
    for(int x:ans) cout<<x<<' ';
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…