Submission #1177525

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177525		irmuun	Library (JOI18_library)	C++20	100 / 100	90 ms	472 KiB

library

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

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const int maxn=1e3;
int n;
vector<int>g[maxn];
vector<int>f;
bool used[maxn];

void dfs(int x){
    used[x]=true;
    for(int y:g[x]){
        if(!used[y]){
            dfs(y);
        }
    }
}

vector<int>ans;
void last(int x,int p){
    ans.pb(x);
    for(int y:g[x]){
        if(y!=p){
            last(y,x);
        }
    }
}

int calc(){
    for(int i=0;i<n;i++){
        used[i]=(f[i]==0?true:false);
    }
    int res=0;
    for(int i=0;i<n;i++){
        if(!used[i]){
            res++;
            dfs(i);
        }
    }
    return res;
}

void Solve(int N){
    n=N;
    if(n==1){
        Answer({1});
        return;
    }
    f.resize(n);
    for(int i=1;i<n;i++){
        fill(f.begin(),f.begin()+i+1,1);
        int cnt=Query(f);
        int my=calc();
        if(my-1==cnt){//one neighbor found
            int lo=0,hi=i-1;
            while(lo<hi){
                int mid=(lo+hi)/2;
                fill(f.begin(),f.begin()+i,0);
                fill(f.begin(),f.begin()+mid+1,1);
                cnt=Query(f);
                my=calc();
                if(cnt==my){
                    lo=mid+1;
                }
                else{
                    hi=mid;
                }
            }
            g[lo].pb(i);
            g[i].pb(lo);
        }
        else if(my-2==cnt){//two neighbor found
            {
                int lo=0,hi=i-1;
                while(lo<hi){
                    int mid=(lo+hi)/2;
                    fill(f.begin(),f.begin()+i,0);
                    fill(f.begin(),f.begin()+mid+1,1);
                    cnt=Query(f);
                    my=calc();
                    if(cnt==my){
                        lo=mid+1;
                    }
                    else{
                        hi=mid;
                    }
                }
                g[lo].pb(i);
                g[i].pb(lo);
            }
            {
                int lo=0,hi=i-1;
                while(lo<hi){
                    int mid=(lo+hi)/2;
                    fill(f.begin(),f.begin()+i,0);
                    fill(f.begin(),f.begin()+mid+1,1);
                    cnt=Query(f);
                    my=calc();
                    if(cnt==my){
                        lo=mid+1;
                    }
                    else{
                        hi=mid;
                    }
                }
                g[lo].pb(i);
                g[i].pb(lo);
            }
        }
    }
    for(int i=0;i<n;i++){
        if(g[i].size()==1){
            last(i,i);
            break;
        }
    }
    for(int &x:ans) x++;
    Answer(ans);
    return;
}

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