답안 #286537

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
286537 2020-08-30T14:16:55 Z gs18115 Travelling Salesperson (CCO20_day2problem1) C++14
0 / 25
1 ms 512 KB
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
int tp[2010][2010];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    for(int i=1;i++<n;)
    {
        string s;
        cin>>s;
        for(int j=1;j<i;j++)
            tp[i][j]=tp[j][i]=s[j-1]=='B'?0:1;
    }
    for(int i=0;i++<n;)
    {
        vector<pi>v0,v1;
        vector<int>vv;
        for(int j=0;j++<n;)
            if(i!=j)
                vv.eb(j);
        if(tp[i][vv.back()]==0)
            v0.eb(i,vv.back());
        else
            v1.eb(i,vv.back());
        vv.pop_back();
        for(int&t:vv)
        {
            int mid=(v0.empty()?v1:v0).back().se;
            int mcol=tp[mid][t];
            if(v0.empty())
            {
                if(mcol==0)
                    v0.eb(t,mid);
                else
                    v1.eb(mid,t);
            }
            else if(v1.empty())
            {
                if(mcol==0)
                    v0.eb(mid,t);
                else
                    v1.eb(t,mid);
            }
            else
            {
                if(mcol==0)
                {
                    v0.eb(mid,t);
                    int ncol=tp[t][v1.back().fi];
                    if(ncol==1)
                        v1.back().se=t;
                    else
                        v0.eb(t,v1.back().fi),v1.pop_back();
                }
                else
                {
                    v1.eb(mid,t);
                    int ncol=tp[t][v0.back().fi];
                    if(ncol==0)
                        v0.back().se=t;
                    else
                        v1.eb(t,v0.back().fi),v0.pop_back();
                }
            }
        }
        vector<int>vv2;
        reverse(all(v1));
        for(pi&t:v0)
            vv2.eb(t.fi),vv2.eb(t.se);
        for(pi&t:v1)
            vv2.eb(t.se),vv2.eb(t.fi);
        vv2.erase(unique(all(vv2)),vv2.end());
        if(vv2[0]!=i)
            reverse(all(vv2));
        cout<<n<<endl;
        for(int&t:vv2)
            cout<<t<<' ';
        cout<<endl;
    }
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Incorrect 1 ms 384 KB Output isn't correct
11 Halted 0 ms 0 KB -