oj.uz

Submission #915436

# Submission time Handle Problem Language Result Execution time Memory
915436 2024-01-23T22:48:07 Z alexdd Library (JOI18_library) C++17
19 / 100
 206 ms 708 KB 
#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;
    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 31 ms 436 KB # of queries: 3462
2 Correct 26 ms 440 KB # of queries: 3418
3 Correct 32 ms 464 KB # of queries: 3596
4 Correct 28 ms 464 KB # of queries: 3552
5 Correct 31 ms 456 KB # of queries: 3588
6 Correct 30 ms 460 KB # of queries: 3584
7 Correct 29 ms 708 KB # of queries: 3558
8 Correct 27 ms 460 KB # of queries: 3400
9 Correct 33 ms 448 KB # of queries: 3598
10 Correct 20 ms 448 KB # of queries: 2180
11 Correct 1 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 0
13 Correct 0 ms 344 KB # of queries: 10
14 Correct 1 ms 344 KB # of queries: 24
15 Correct 1 ms 344 KB # of queries: 152
16 Correct 3 ms 344 KB # of queries: 320

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 436 KB # of queries: 3462
2 Correct 26 ms 440 KB # of queries: 3418
3 Correct 32 ms 464 KB # of queries: 3596
4 Correct 28 ms 464 KB # of queries: 3552
5 Correct 31 ms 456 KB # of queries: 3588
6 Correct 30 ms 460 KB # of queries: 3584
7 Correct 29 ms 708 KB # of queries: 3558
8 Correct 27 ms 460 KB # of queries: 3400
9 Correct 33 ms 448 KB # of queries: 3598
10 Correct 20 ms 448 KB # of queries: 2180
11 Correct 1 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 0
13 Correct 0 ms 344 KB # of queries: 10
14 Correct 1 ms 344 KB # of queries: 24
15 Correct 1 ms 344 KB # of queries: 152
16 Correct 3 ms 344 KB # of queries: 320
17 Runtime error 206 ms 460 KB Execution killed with signal 13
18 Halted 0 ms 0 KB -