Submission #1166890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166890		trandangquang	Library (JOI18_library)	C++20	100 / 100	68 ms	524 KiB

library

#include"library.h"

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

/// interactor's
//int Query(const vector<int>& M){
//    for(int i:M) cout<<i<<" ";
//    cout<<endl;
//    int x; cin>>x;
//    return x;
//}
//void Answer(const vector<int>& res){
//    cout<<"! ";
//    for(int i:res) cout<<i<<" ";
//    return;
//}

const int N=1010;

int n,suf[N]; bool vis[N];
vector<int> adj[N]; // adjacency on the bookshelf
vector<int> res,q;

void calc(int l, int r, vector<pair<int,int>>v){
    // v is vector contain pairs {index, number of indexes adjacent to it from l->r}
    if(l>r || v.empty()) return;
    if(l==r){
        for(pair<int,int> i:v) if(i.second) adj[i.first].emplace_back(l), adj[l].emplace_back(i.first);
        return;
    }

    int mid=(l+r)>>1, tmp=0;
    q.assign(n,0);
    for(int i=mid+1; i<=r; ++i) q[i]=1;
    tmp=Query(q);

    vector<pair<int,int>> vL,vR;
    for(pair<int,int> i:v){
        if(i.first>=mid+1) vR.emplace_back(i);
        else{
            q[i.first]=1;
            int x=Query(q);
            if(i.second-(tmp-x+1)>0) vL.emplace_back(i.first,i.second-(tmp-x+1));
            if(tmp-x+1>0) vR.emplace_back(i.first,tmp-x+1);
            q[i.first]=0;
        }
    }
    calc(l,mid,vL); calc(mid+1,r,vR);
}
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<pair<int,int>> s;

    // suf[i]: number of components when took book from i->n-1
    q.resize(n);
    suf[n-1]=1; q[n-1]=1;
    for(int i=n-2; i>=0; --i){
        q[i]=1;
        suf[i]=Query(q);
        if(suf[i+1]-suf[i]+1>0) s.emplace_back(i,suf[i+1]-suf[i]+1);
    }
    calc(0,n-1,s);
    for(int i=0; i<n; ++i){
        if(adj[i].size()==1){
            dfs(i);
            break;
        }
    }
    Answer(res);
}

//int main(){
//    Solve(5);
//}

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