Submission #213247

#	Time	Username	Problem	Language	Result	Execution time	Memory
213247		brcode	Library (JOI18_library)	C++14	0 / 100	1209 ms	262148 KiB

library

#include <iostream>
#include "library.h"

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1010;
deque<int> l;
vector<int> g[MAXN];
deque<int> r;
vector<int> ord;
int cnt;
vector<int> rem;
vector<int> templ;
vector<int> tempr;
deque<int> curr;
vector<int> tempq;
int deg[MAXN];
/*int Query(vector<int> x){
    for(int y:x){
        cout<<y<<" ";
    }
    cnt++;
    
    cout<<endl;
    if(cnt == 1){
        cout<<2<<endl;
        return 2;
    }
    if(cnt == 2){
        cout<<1<<endl;
        return 1;
    }
    if(cnt==3){
        cout<<2<<endl;
        return 2;
    }
    if(cnt==4){
        cout<<3<<endl;
        return 3;
    }
    if(cnt==5){
        cout<<2<<endl;
        return 2;
    }
    if(cnt == 6){
        cout<<2<<endl;
        return 0;
    }
    if(cnt==7){
        cout<<1<<endl;
        return 0;
    }
    if(cnt ==8){
        cout<<1<<endl;
        return 0;
    }
    if(cnt==9){
        cout<<1<<endl;
        return 1;
    }
    if(cnt==10){
        cout<<2<<endl;
        return 2;
    }
    if(cnt == 11){
        cout<<1<<endl;
        return 0;
    }
    return 1;
}
void Answer(vector<int> x){
    for(int y:x){
        cout<<y<<" ";
    }
    cout<<endl;
}*/
void toQuery(int x,deque<int> v1,int sz){
    int n = v1.size();
    for(int i=0;i<sz;i++){
        tempq[i] = 0;
       //cout<<sz<<endl;
    }
    bool check = false;
    if(n==1){
        g[x].push_back(v1[0]);
        g[v1[0]].push_back(x);
        deg[x]++;
        deg[v1[0]]++;
        
        if(deg[v1[0]] == 2){
            //cout<<x<<" "<<v1[0]<<endl;
            rem.push_back(v1[0]);
        }
        return;
    }

    deque<int> d1;
    
    for(int i=0;i<(n/2);i++){
        
        tempq[v1[i]-1] = 1;
        
        tempq[x-1] = 0;
        d1.push_back(v1[i]);
        
    }
    
    
    int A;
    if(d1.size()>1){
        A= Query(tempq);
    }else{
        A=1;
    }
    tempq[x-1] = 1;
    int nxt = Query(tempq);
    if(nxt<=A){
         toQuery(x,d1,sz);
    }else{
        check = true;
    }
    d1.clear();
    for(int i=0;i<(n/2);i++){
        tempq[v1[i]-1] = 0;
    }
    for(int i=(n/2);i<(n);i++){
        
        tempq[v1[i]-1] = 1;
       // cout<<v1[i-1]<<" ";
        tempq[x-1] = 0;
        d1.push_back(v1[i]);
        
    }
    if(check && deg[x]==0){
        toQuery(x,d1,sz);
        return;
    }

    
    int B;
    if(d1.size() == 0){
        return;
    }
    if(d1.size() == 1){
        B=1;
    }else{
        B= Query(tempq);
    }
    tempq[x-1] = 1;
    nxt = Query(tempq);
    if(nxt<=B){
       
         toQuery(x,d1,sz);
    }
}
void dfs(int curr,int par){
    ord.push_back(curr);
    for(int x:g[curr]){
        if(x!=par){
            dfs(x,curr);
        }
    }
}
void clearQ(int n){
    for(int i=0;i<n;i++){
        tempq[i] = 0;
    }
}
void Solve(int N){
    int n = N;
    if(n==1){
        vector<int> res;
        res.push_back(1);
        Answer(res);
        return;
    }
    for(int i=1;i<=n;i++){
        //tempq = vector we use for Querying
        tempq.push_back(0);
    }
    for(int i=1;i<=(N/2);i++){
        l.push_back(i);
        
        //l subarray
    }

    for(int i=(N/2)+1;i<=N;i++){
        r.push_back(i);
        //r subarray
    }

    for(int i=1;i<=n;i++){
        if(i<=(n/2)){
            if(l.size() && l.front() == i){
               
                l.pop_front();
               
            }
        }else{
           
            if(r.size() && r.front() == i){
                
                r.pop_front();
            }
        }
        clearQ(n);
        if(l.size()){

            if(l.size()==1){
                tempq[l[0]-1] = 1;
                tempq[i-1] = 1;
                if(Query(tempq) == 1){
                  
                    toQuery(i,l,n);
                }
            }else{
                toQuery(i,l,n);
            }
        }
        for(int x:rem){
         
            //cout<<123<<endl;
            if(x<=(N/2)){
                for(int y:l){
                    if(y==x){
                        continue;
                    }else{
                        templ.push_back(y);
                    }
                }
                l.clear();
                for(int y:templ){
                    l.push_back(y);
                }
                templ.clear();
            }else{
                for(int y:r){
                    if(y==x){
                        continue;
                    }else{
                        tempr.push_back(y);
                    }
                }
                r.clear();
                for(int y:tempr){
                    r.push_back(y);
                }
                tempr.clear();
            }
        }
        
        rem.clear();
        clearQ(n);
        if(r.size()){
            
            if(r.size() == 1){
                tempq[r[0]-1] = 1;
                tempq[i-1] = 1;
                if(Query(tempq) == 1){
                    toQuery(i,r,n);
                }
            }else{
                toQuery(i,r,n);
            }
        }
        for(int x:rem){
         
            if(x<=(N/2)){
                for(int y:l){
                    if(y==x){
                        continue;
                    }else{
                        templ.push_back(y);
                    }
                }
              
                l.clear();
                for(int y:templ){
                    l.push_back(y);
                }
                 templ.clear();
            }else{
                for(int y:r){
                    
                    if(y==x){
                        continue;
                    }else{
                        tempr.push_back(y);
                    }
                }
                r.clear();
                for(int y:tempr){
                    r.push_back(y);
                   
                }
                tempr.clear();
            }
        }
        
        rem.clear();
    }
    for(int i=1;i<=n;i++){
        if(deg[i] == 1){
            dfs(i,i);
            break;
        }
    }
    Answer(ord);
}
/*int main(){
    Solve(5);
}*/

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