제출 #915433

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
915433		alexdd	도서관 (JOI18_library)	C++17	19 / 100	204 ms	708 KiB

library

#include <bits/stdc++.h>
#include "library.h"
using namespace std;
int n;
vector<int> con[1005];
vector<pair<int,int>> vecini;
int intreaba(int le, int ri)
{
    le--;
    ri--;
    vector<int> cv(n);
    for(int i=0;i<n;i++)
    {
        if(le<=i && i<=ri)
            cv[i]=1;
        else
            cv[i]=0;
    }
    return Query(cv);
}
vector<int> ord;
void dfs(int nod, int par)
{
    ord.push_back(nod);
    for(auto adj:con[nod])
    {
        if(adj!=par)
        {
            dfs(adj,nod);
        }
    }
}
void Solve(int N)
{
    n=N;
    if(n<=2)
    {
        for(int i=1;i<=n;i++)
            ord.push_back(i);
        Answer(ord);
        return;
    }
    for(int i=2;i<=n;i++)
    {
        if(intreaba(1,i)==intreaba(1,i-1))
        {
            //cerr<<"caz 1\n";
            ///am un vecin
            int st,dr,mij,ans=1;
            st=1;
            dr=i-1;
            while(st<=dr)
            {
                mij=(st+dr)/2;
                if(intreaba(mij,i)==intreaba(mij,i-1))
                {
                    ans=mij;
                    st=mij+1;
                }
                else
                    dr=mij-1;
            }
            vecini.push_back({ans,i});
        }
        else if(intreaba(1,i)==intreaba(1,i-1)+1)
        {
            //cerr<<"caz 2\n";
            ///nu fac nimic
        }
        else if(intreaba(1,i)==intreaba(1,i-1)-1)
        {
            //cerr<<"caz 3\n";
            //continue;
            ///am 2 vecini
            int st,dr,mij,ans=1;
            st=1;
            dr=i-1;
            while(st<=dr)
            {
                mij=(st+dr)/2;
                if(intreaba(mij,i)<intreaba(mij,i-1))
                {
                    ans=mij;
                    st=mij+1;
                }
                else
                    dr=mij-1;
            }
            vecini.push_back({ans,i});

            ans=1;
            st=1;
            dr=i-1;
            while(st<=dr)
            {
                mij=(st+dr)/2;
                if(intreaba(mij,i)<=intreaba(mij,i-1))
                {
                    ans=mij;
                    st=mij+1;
                }
                else
                    dr=mij-1;
            }
            vecini.push_back({ans,i});
        }
    }
    //for(auto x:vecini)
      //  cerr<<x.first<<" "<<x.second<<" zzz\n";
    for(auto x:vecini)
    {
        con[x.first].push_back(x.second);
        con[x.second].push_back(x.first);
    }
    int capat=-1;
    for(int i=n;i>0;i--)
        if((int)con[i].size()==1)
            capat=i;
    dfs(capat,0);
    //for(auto x:ord)
      //  cout<<x<<" ";

    Answer(ord);
}
/**
5
1 3 2 5 4

5
5 4 3 2 1

*/

• Subtask 1: 19 / 19
• Subtask 2: 0 / 81