Submission #227515

#	Time	Username	Problem	Language	Result	Execution time	Memory
227515		MKopchev	Library (JOI18_library)	C++14	100 / 100	403 ms	2944 KiB

library

#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 / 19
• Subtask 2: 81 / 81