oj.uz

Submission #227515

# Submission time Handle Problem Language Result Execution time Memory
227515 2020-04-27T15:45:29 Z MKopchev Library (JOI18_library) C++14
100 / 100
 403 ms 2944 KB 
#include "library.h"
#include <bits/stdc++.h>
using namespace std;

const int nmax=1e5+42;

vector<int> adj[nmax];
/*
vector<int> order={4,2,5,3,1};

int Query(vector<int> in)
{
    bool active=0;
    int ret=0;
    for(auto k:order)
    {
        if(in[k-1])
        {
            if(active==0)ret++;
            active=1;
        }
        else active=0;
    }
    return ret;
}
void Answer(vector<int> outp)
{
    for(auto k:outp)printf("%i ",k);
}
*/
vector<int> outp;
void dfs(int node,int par)
{
    outp.push_back(node+1);
    for(auto k:adj[node])
        if(k!=par)dfs(k,node);

}

int N;

vector< pair<int,int> > noted;

bool is_equal(int l,int r)
{
    vector<int> help={};
    for(int i=0;i<N;i++)
        if(l<=i&&i<=r)help.push_back(1);
        else help.push_back(0);

    int current=Query(help);

    for(auto k:noted)
        if(help[k.first]&&help[k.second])current++;

    return current==r-l+1;
}

void Solve(int n_)
{
    N=n_;
    if(n_==1)
    {
        Answer({1});
    }

    for(int i=0;i<n_;)
    {
        if(is_equal(0,i))
        {
            i++;
            continue;
        }

        int ok=0,not_ok=i;
        while(not_ok-ok>1)
        {
            int av=(ok+not_ok)/2;
            if(is_equal(av,i))not_ok=av;
            else ok=av;
        }

        //cout<<"edge "<<i<<" "<<ok<<endl;

        noted.push_back({i,ok});

        adj[i].push_back(ok);
        adj[ok].push_back(i);
    }

    for(int i=0;i<n_;i++)
        if(adj[i].size()==1)
        {
            dfs(i,-1);
            Answer(outp);
            return;
        }

}
/*
int main()
{
    Solve(5);

    return 0;
}
*/

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2688 KB # of queries: 1714
2 Correct 42 ms 2688 KB # of queries: 1707
3 Correct 36 ms 2688 KB # of queries: 1787
4 Correct 48 ms 2688 KB # of queries: 1784
5 Correct 43 ms 2688 KB # of queries: 1797
6 Correct 39 ms 2688 KB # of queries: 1792
7 Correct 38 ms 2688 KB # of queries: 1785
8 Correct 39 ms 2808 KB # of queries: 1687
9 Correct 42 ms 2720 KB # of queries: 1789
10 Correct 28 ms 2688 KB # of queries: 1078
11 Correct 6 ms 2688 KB # of queries: 1
12 Correct 6 ms 2688 KB # of queries: 3
13 Correct 6 ms 2688 KB # of queries: 6
14 Correct 6 ms 2688 KB # of queries: 11
15 Correct 7 ms 2688 KB # of queries: 76
16 Correct 9 ms 2688 KB # of queries: 159

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2688 KB # of queries: 1714
2 Correct 42 ms 2688 KB # of queries: 1707
3 Correct 36 ms 2688 KB # of queries: 1787
4 Correct 48 ms 2688 KB # of queries: 1784
5 Correct 43 ms 2688 KB # of queries: 1797
6 Correct 39 ms 2688 KB # of queries: 1792
7 Correct 38 ms 2688 KB # of queries: 1785
8 Correct 39 ms 2808 KB # of queries: 1687
9 Correct 42 ms 2720 KB # of queries: 1789
10 Correct 28 ms 2688 KB # of queries: 1078
11 Correct 6 ms 2688 KB # of queries: 1
12 Correct 6 ms 2688 KB # of queries: 3
13 Correct 6 ms 2688 KB # of queries: 6
14 Correct 6 ms 2688 KB # of queries: 11
15 Correct 7 ms 2688 KB # of queries: 76
16 Correct 9 ms 2688 KB # of queries: 159
17 Correct 393 ms 2784 KB # of queries: 11318
18 Correct 403 ms 2796 KB # of queries: 11163
19 Correct 383 ms 2944 KB # of queries: 11288
20 Correct 352 ms 2936 KB # of queries: 10562
21 Correct 336 ms 2936 KB # of queries: 9929
22 Correct 398 ms 2808 KB # of queries: 11301
23 Correct 398 ms 2808 KB # of queries: 11270
24 Correct 131 ms 2688 KB # of queries: 5299
25 Correct 395 ms 2808 KB # of queries: 11039
26 Correct 302 ms 2812 KB # of queries: 10331
27 Correct 131 ms 2688 KB # of queries: 5280
28 Correct 388 ms 2808 KB # of queries: 10966
29 Correct 320 ms 2936 KB # of queries: 10954
30 Correct 317 ms 2808 KB # of queries: 10966