Submission #963515

#	Time	Username	Problem	Language	Result	Execution time	Memory
963515		12345678	Library (JOI18_library)	C++17	100 / 100	224 ms	716 KiB

library

#include <bits/stdc++.h>
#include "library.h"
using namespace std;

const int nx=1005;
int n, s=1;
vector<pair<int, int>> edg;
vector<int> v[nx], res;

int query(int l, int r)
{
    vector<int> qrs(n);
    for (int i=l; i<=r; i++) qrs[i-1]=1;
    int cnt=0;
    for (auto [x, y]:edg) if (l<=x&&y<=r) cnt++;
    return Query(qrs)+cnt;
}

void find_edge()
{
    int l=1, r=n;
    /*
    cout<<"test query : ";
    for (int i=1; i<=n; i++) cout<<query(1, i)<<' ';
    cout<<'\n'; */
    while (l<r)
    {
        int md=(l+r)/2;
        if (query(1, md)==md) l=md+1;
        else r=md;
    }
    int tmp=l;
    l=1, r=tmp;
    while (l<r)
    {
        int md=(l+r+1)/2;
        if (query(md, tmp)==tmp-md+1) r=md-1;
        else l=md;
    }
    edg.push_back({l, tmp});
    //cout<<"edge "<<l<<' '<<tmp<<'\n';
    //cout<<"debug "<<query(1, n)<<'\n';
}

void dfs(int u, int p)
{
	res.push_back(u);
	for (auto x:v[u]) if (x!=p) dfs(x, u);
}

void Solve(int N)
{
    n=N;
    //cout<<"test "<<query(1, n)<<'\n';
	for (int i=1; i<N; i++) find_edge();
    for (auto [x, y]:edg) v[x].push_back(y), v[y].push_back(x);
	for (int i=1; i<=N; i++) if (v[i].size()==1) s=i;
	dfs(s, s);
	Answer(res);
}

• Subtask 1: 19 / 19
• Subtask 2: 81 / 81