Submission #1184105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184105		ivaziva	Library (JOI18_library)	C++20	0 / 100	12 ms	320 KiB

library

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

using namespace std;

#define MAXN 1001

int pref[MAXN];
vector<int> adj[MAXN],vec,ans;

void dfs(int node,int pret)
{
    ans.push_back(node);
    for (int sled:adj[node])
    {
        if (sled!=pret) dfs(sled,node);
    }
}

void Solve(int n)
{
    for (int i=0;i<n;i++) vec.push_back(0);
    for (int i=2;i<=n;i++)
    {
        for (int j=0;j<i-1;j++) vec[j]=1;
        pref[i-1]=Query(vec);for (int j=0;j<i-1;j++) vec[j]=0;
        if (adj[i].size()==1) continue;
        int l=1,r=i-1,rez=-1;vec[i-1]=1;
        while (l<=r)
        {
            int mid=(l+r)/2;
            for (int j=0;j<mid;j++) vec[j]=1;
            int sol=Query(vec);
            if (sol==pref[mid]) {rez=mid;r=mid-1;}
            else l=mid+1;
            for (int j=0;j<mid;j++) vec[j]=0;
        }
        if (rez!=-1) {adj[i].push_back(rez);adj[rez].push_back(i);}
        vec[i-1]=0;
    }
    for (int i=1;i<=n;i++) pref[i]=0;
    for (int i=n-1;i>=1;i--)
    {
        for (int j=i;j<n;j++) vec[j]=1;
        pref[i+1]=Query(vec);for (int j=i;j<n;j++) vec[j]=0;
        if (adj[i].size()==2) continue;
        int sused=i;if (adj[i].size()==1) sused=adj[i][0];
        int l=max(sused,i)+1,r=n,rez=-1;vec[i-1]=1;
        while (l<=r)
        {
            int mid=(l+r)/2;
            for (int j=mid-1;j<n;j++) vec[j]=1;
            int sol=Query(vec);
            if (sol==pref[mid]) {rez=mid;l=mid+1;}
            else r=mid-1;
            for (int j=mid-1;j<n;j++) vec[j]=0;
        }
        if (rez!=-1) {adj[i].push_back(rez);adj[rez].push_back(i);}
        vec[i-1]=0;
    }
    for (int i=1;i<=n;i++)
    {
        if (adj[i].size()==1) {dfs(i,0);break;}
    }
    if (ans.size()==n) {Answer(ans);return;}
    int node=-1;
    for (int i=1;i<=n;i++)
    {
        if (adj[i].size()!=2 and node==-1 and i!=ans[0] and i!=ans[ans.size()-1]) {node=i;break;}
    }
    for (int i=0;i<n;i++) vec[i]=0;
    vec[node-1]=1;vec[ans[0]-1]=1;
    if (Query(vec)==1) {adj[node].push_back(ans[0]);adj[ans[0]].push_back(node);}
    else {adj[node].push_back(ans[ans.size()-1]);adj[ans[ans.size()-1]].push_back(node);}
    ans.clear();
    for (int i=1;i<=n;i++)
    {
        if (adj[i].size()==1) {dfs(i,0);break;}
    }
    Answer(ans);
}

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