Submission #111451

#	Time	Username	Problem	Language	Result	Execution time	Memory
111451		igzi	Library (JOI18_library)	C++17	100 / 100	513 ms	684 KiB

library

#include <bits/stdc++.h>
#define maxN 1005
#include "library.h"

using namespace std;

vector <int> adj[maxN];
int N;

int upit(int l,int d,int x){
vector<int> v(N);
if(x!=-1) v[x-1]=1;
for(int i=l;i<=d;i++) v[i-1]=1;
return Query(v);
}

void resi1(int l,int d,int x){
if(l==d){
    adj[x].push_back(l);
    adj[l].push_back(x);
    return;
}
int m=(l+d)/2;
if(upit(l,m,x)-upit(l,m,-1)==0) resi1(l,m,x);
else resi1(m+1,d,x);
}

void resi2(int l,int d,int x){
int m=(l+d)/2;
int tmp=upit(l,m,x)-upit(l,m,-1);
if(tmp==-1) resi2(l,m,x);
if(tmp==1) resi2(m+1,d,x);
if(tmp==0) {resi1(l,m,x); resi1(m+1,d,x);}
}

vector <int> res;

void dfs(int n,int par){
res.push_back(n);
if(adj[n][0]!=par) dfs(adj[n][0],n);
else{
    if(adj[n].size()==1) return;
    dfs(adj[n][1],n);
}
}

void Solve(int n)
{
    N=n;
    if(n==1){
        res.push_back(1);
        Answer(res);
        return;
    }
	for(int i=2;i<=n;i++){
        int tmp=upit(1,i-1,i)-upit(1,i-1,-1);
        if(tmp==-1) resi2(1,i-1,i);
        if(tmp==0) resi1(1,i-1,i);
	}
	for(int i=1;i<=n;i++){
        if(adj[i].size()==1){
            dfs(i,-1);
            break;
        }
	}
	Answer(res);
}

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