Submission #286544

#	Time	Username	Problem	Language	Result	Execution time	Memory
286544		gs18115	Travelling Salesperson (CCO20_day2problem1)	C++14	25 / 25	595 ms	36264 KiB

Main

#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;
            if(mid==i)
            {
                if(v0.empty())
                {
                    for(pi&t:v1)
                        swap(t.fi,t.se);
                    reverse(all(v1));
                }
                else
                {
                    for(pi&t:v0)
                        swap(t.fi,t.se);
                    reverse(all(v0));
                }
                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;
}

• Subtask 1: 25 / 25