제출 #1166883

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166883		trandangquang	도서관 (JOI18_library)	C++20	0 / 100	191 ms	327680 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];
vector<int> adj[N]; // adjacency on the bookshelf
vector<int> res;

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;
//    cerr<<l<<" "<<r<<endl;
//    for(pair<int,int>i:v) cerr<<i.first<<" "<<i.second<<endl;

    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;
    vector<int> q(n);
    for(int i=mid+1; i<n; ++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, int p){
    res.emplace_back(u+1);
    for(int v:adj[u]) if(v!=p){
        dfs(v,u);
    }
}
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
    vector<int> q(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);
//        cerr<<i<<" "<<suf[i+1]-suf[i]+1<<'\n';
    }
    calc(0,n-1,s);
    for(int i=0; i<n; ++i){
        if(adj[i].size()==1){
            dfs(i,i);
            break;
        }
    }
    Answer(res);
}

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

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