Submission #1366895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1366895		biserailieva	Carnival (EGOI23_carnival)	C++20	40 / 100	1094 ms	2992 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin>>n;
    if(n<=8)
    {
        vector<vector<int>>V(n);
        for(int i=0;i<n-1;i++)
        {
            for(int j=0;j<i+1;j++)
            {
                int x;
                cin>>x;
                if(j>=(i+2)/2)
                {
                    V[i+1].push_back(x);
                    V[x].push_back(i+1);
                }
            }
        }
        int A[n];
        for(int i=0;i<n;i++)
        {
            A[i]=i;
        }
        bool valid;
        do
        {
            valid=true;
            for(int i=0;i+1<n;i++)
            {
                for(int br : V[A[i]])
                {
                    if(br==A[i+1])
                    {
                        valid=false;
                    }
                }
                for(int br : V[A[i+1]])
                {
                    if(br==A[i])
                    {
                        valid=false;
                    }
                }
            }
            if(valid)
            {
                for(int i=0;i<n;i++)
                {
                    cout<<A[i]<<' ';
                }
                cout<<endl;
                return 0;
            }
            
        }while(next_permutation(A, A+n));
    }
    vector<int>V[n];
    bool s=true, rev=true;
    for(int i=0;i<n-1;i++)
    {
        vector<int>A;
        for(int j=0;j<i+1;j++)
        {
            int x;
            cin>>x;
            V[i].push_back(x);
            A.push_back(x);
        }
        sort(A.begin(), A.end());
        if(A!=V[i])
        {
            s=false;
        }
        reverse(A.begin(), A.end());
        if(A!=V[i])
        {
            rev=false;
        }
    }
    if(rev)
    {
        for(int i=0;i<n;i++)
        {
            cout<<i<<' ';
        }
        cout<<endl;
    }
    else if(s)
    {
        vector<int>dozv[n];
        for(int i=n-1;i>=0;i--)
        {
            for(int j=0;j<=n-1;j++)
            {
                if(i==j)
                {
                    continue;
                }
                if(j>=(i+1)/2)
                {
                    continue;
                }
                if(dozv[j].empty())
                {
                    dozv[i].push_back(j);
                }
                else
                {
                    for(int br : dozv[j])
                    {
                        if(br==i)
                        {
                            dozv[i].push_back(br);
                        }
                    }
                }
            }
        }
        deque<int>dq;
        set<int>used;
        dq.push_back(0);
        dq.push_back(n/2);
        dq.push_front(n/2+1);
        used.insert(0);
        used.insert(n/2);
        used.insert(n/2+1);
        int step=0;
        while(dq.size()<n)
        {
            if(step==0)
            {
                int x=dq.front();
                for(int d : dozv[x])
                {
                    if(used.find(d)!=used.end())
                    {
                        dq.push_front(d);
                        used.insert(d);
                        break;
                    }
                }
                step=1;
            }
            else
            {
                int x=dq.back();
                for(int d : dozv[x])
                {
                    if(used.find(d)!=used.end())
                    {
                        dq.push_back(d);
                        used.insert(d);
                        break;
                    }
                }
                step=0;
            }
        }
        for(int d : dq)
        {
            cout<<d<<' ';
        }
        cout<<endl;
    }
    return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 11 / 11
• Subtask 2: 0 / 23
• Subtask 3: 29 / 29
• Subtask 4: 0 / 37