oj.uz

Submission #915437

# Submission time Handle Problem Language Result Execution time Memory
915437 2024-01-23T22:50:07 Z alexdd Library (JOI18_library) C++17
100 / 100
 200 ms 3036 KB 
#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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 996 KB # of queries: 2379
2 Correct 25 ms 1032 KB # of queries: 2446
3 Correct 27 ms 1228 KB # of queries: 2510
4 Correct 23 ms 1340 KB # of queries: 2554
5 Correct 23 ms 1548 KB # of queries: 2547
6 Correct 24 ms 1240 KB # of queries: 2516
7 Correct 21 ms 1260 KB # of queries: 2571
8 Correct 19 ms 1308 KB # of queries: 2426
9 Correct 20 ms 1744 KB # of queries: 2500
10 Correct 15 ms 972 KB # of queries: 1475
11 Correct 1 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 0
13 Correct 1 ms 340 KB # of queries: 5
14 Correct 1 ms 596 KB # of queries: 9
15 Correct 1 ms 460 KB # of queries: 73
16 Correct 2 ms 660 KB # of queries: 178

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 996 KB # of queries: 2379
2 Correct 25 ms 1032 KB # of queries: 2446
3 Correct 27 ms 1228 KB # of queries: 2510
4 Correct 23 ms 1340 KB # of queries: 2554
5 Correct 23 ms 1548 KB # of queries: 2547
6 Correct 24 ms 1240 KB # of queries: 2516
7 Correct 21 ms 1260 KB # of queries: 2571
8 Correct 19 ms 1308 KB # of queries: 2426
9 Correct 20 ms 1744 KB # of queries: 2500
10 Correct 15 ms 972 KB # of queries: 1475
11 Correct 1 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 0
13 Correct 1 ms 340 KB # of queries: 5
14 Correct 1 ms 596 KB # of queries: 9
15 Correct 1 ms 460 KB # of queries: 73
16 Correct 2 ms 660 KB # of queries: 178
17 Correct 189 ms 2376 KB # of queries: 17498
18 Correct 196 ms 2636 KB # of queries: 17198
19 Correct 200 ms 2340 KB # of queries: 17423
20 Correct 172 ms 2420 KB # of queries: 16200
21 Correct 166 ms 2412 KB # of queries: 15270
22 Correct 197 ms 2984 KB # of queries: 17370
23 Correct 188 ms 2724 KB # of queries: 17501
24 Correct 87 ms 1776 KB # of queries: 7905
25 Correct 182 ms 3036 KB # of queries: 17037
26 Correct 187 ms 2388 KB # of queries: 15879
27 Correct 78 ms 1928 KB # of queries: 7918
28 Correct 165 ms 2096 KB # of queries: 16469
29 Correct 196 ms 2464 KB # of queries: 16449
30 Correct 172 ms 2232 KB # of queries: 16469