Submission #1172722

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172722		AlgorithmWarrior	Library (JOI18_library)	C++20	100 / 100	77 ms	836 KiB

library

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

using namespace std;

vector<int>ask(int id,int N,vector<deque<int>>& rasp){
    vector<int>intrb(N,0);
    int i;
    for(i=0;i<=id;++i)
        for(auto elem : rasp[i])
            intrb[elem-1]=1;
    return intrb;
}

void upgrade(int N,vector<deque<int>>& rasp,int nr){
    vector<int>intrb=ask((int)rasp.size()-1,N,rasp);
    intrb[nr-1]=1;
    if(Query(intrb)==(int)rasp.size()+1)
        rasp.push_back({nr});
    else
        if(Query(intrb)==(int)rasp.size()){
            int st=-1,dr=(int)rasp.size()-1;
            /// (]
            while(dr-st>1){
                int mij=(st+dr)/2;
                intrb=ask(mij,N,rasp);
                intrb[nr-1]=1;
                if(Query(intrb)==mij+1)
                    dr=mij;
                else
                    st=mij;
            }
            fill(intrb.begin(),intrb.end(),0);
            intrb[nr-1]=1;
            intrb[rasp[dr].front()-1]=1;
            if(Query(intrb)==1)
                rasp[dr].push_front(nr);
            else
                rasp[dr].push_back(nr);
        }
        else{
            int st=-1,dr=(int)rasp.size()-1;
            while(dr-st>1){
                int mij=(st+dr)/2;
                intrb=ask(mij,N,rasp);
                intrb[nr-1]=1;
                if(Query(intrb)<=mij+1)
                    dr=mij;
                else
                    st=mij;
            }
            int id1=dr;
            st=-1,dr=(int)rasp.size()-1;
            while(dr-st>1){
                int mij=(st+dr)/2;
                intrb=ask(mij,N,rasp);
                intrb[nr-1]=1;
                if(Query(intrb)==mij)
                    dr=mij;
                else
                    st=mij;
            }
            int id2=dr;
            deque<int>deq1=rasp[id1];
            deque<int>deq2=rasp[id2];
            rasp[id1].clear();
            rasp[id2].clear();
            fill(intrb.begin(),intrb.end(),0);
            intrb[nr-1]=1;
            intrb[deq1.front()-1]=1;
            if(Query(intrb)==1){
                deq1.push_front(nr);
                reverse(deq1.begin(),deq1.end());
            }
            else
                deq1.push_back(nr);
            fill(intrb.begin(),intrb.end(),0);
            intrb[nr-1]=1;
            intrb[deq2.back()-1]=1;
            if(Query(intrb)==1)
                reverse(deq2.begin(),deq2.end());
            while(!deq2.empty()){
                deq1.push_back(deq2.front());
                deq2.pop_front();
            }
            rasp[id1]=deq1;
            vector<deque<int>>nou;
            for(auto dq : rasp)
                if(!dq.empty())
                    nou.push_back(dq);
            rasp=nou;
        }
}

void Solve(int N)
{
    vector<deque<int>>rasp;
    int i;
    for(i=1;i<=N;++i)
        upgrade(N,rasp,i);
    vector<int>ans;
    for(auto elem : rasp[0])
        ans.push_back(elem);
    Answer(ans);
}

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