Submission #915437

#	Time	Username	Problem	Language	Result	Execution time	Memory
915437		alexdd	Library (JOI18_library)	C++17	100 / 100	200 ms	3036 KiB

library

#include <bits/stdc++.h>
#include "library.h"
using namespace std;
int n;
vector<int> con[1005];
vector<pair<int,int>> vecini;
map<pair<int,int>,pair<int,bool>> prec;
int intreaba(int le, int ri)
{
    le--;
    ri--;
    if(prec[{le,ri}].second==0)
    {
        vector<int> cv(n);
        for(int i=0;i<n;i++)
        {
            if(le<=i && i<=ri)
                cv[i]=1;
            else
                cv[i]=0;
        }
        prec[{le,ri}] = {Query(cv),1};
    }
    return prec[{le,ri}].first;
}
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;
    if(capat==-1)
    {
        while(1)
            n=0;
    }
    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: 81 / 81