Submission #1167116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167116		trandangquang	Library (JOI18_library)	C++20	100 / 100	121 ms	480 KiB

library

#include"library.h"

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

// interactor's
// int Query(const vector<int>& M){
//     vector<int>haiz={1,2};
//     int hi=haiz.size();
//     vector<int> lm(hi);
//     for(int j=0; j<hi; ++j){
//         if(M[j]==1){
//             for(int i=0; i<hi; ++i) if(haiz[i]==j+1) lm[i]=1;
//         }       
//     }
//     int res=lm[0]==1;
//     for(int i=1; i<hi; ++i) res+=(lm[i-1]==0&&lm[i]==1);
//     return res;
// }
// void Answer(const vector<int>& res){
//     cout<<"! ";
//     for(int i:res) cout<<i<<" ";
//     cout<<endl;  
// }
// 

const int N=1010;

int n,suf[N]; bool vis[N];
vector<int> adj[N],res;

void dfs(int u){
    vis[u]=true; res.emplace_back(u+1);
    for(int v:adj[u]) if(!vis[v]) dfs(v);   
}

void Solve(int _n){
    n=_n;
    if(n==1) return Answer({1}), void();
    
    vector<int> v(n);
    suf[n-1]=1; v[n-1]=1;
    for(int i=n-2; i>=0; --i){
        v[i]=1;
        suf[i]=Query(v);
    }
    for(int _=0; _<n; ++_) v[_]=0;

    for(int i=0; i<n; ++i){
        for(int j=0; j<2; ++j){
            int l=i+1,r=n-1,res=-1;
            while(l<=r){
                int m=(l+r)>>1;
                
                for(int _=0; _<n; ++_) v[_]=0;
                v[i]=1;
                for(int _=m; _<n; ++_) v[_]=1;
                int tmp=Query(v);

                if(suf[m]-tmp+1>j){
                    res=m;
                    l=m+1;   
                }   
                else{
                    r=m-1;
                }
            }       
            if(res==-1) break;
            adj[res].emplace_back(i);
            adj[i].emplace_back(res);
        }
    } 

    for(int i=0; i<n; ++i){
        if(adj[i].size()==1){
            dfs(i);
            break;
        }  
    }
    Answer(res);
}   

// int main(){
//     cin.tie(0)->sync_with_stdio(0);
//     Solve(2);
// }

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