Submission #1134788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134788		StefanSebez	Library (JOI18_library)	C++20	100 / 100	116 ms	464 KiB

library

#include <bits/stdc++.h>
#include "library.h"
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
void Solve(int n){
	vector<int>temp(n,0);
	vector<vector<int>>komp;
	for(int i=0;i<n;i++){
        for(int j=0;j<n;j++) temp[j]=0;
        for(auto j:komp) for(auto k:j) temp[k]=1;
        bool allzero=true;for(auto j:temp) if(temp[j]) allzero=false;
        int x=0;
        if(!allzero) x=Query(temp);
        temp[i]=1;
        int x1=Query(temp);
        if(x<x1){
            komp.pb({i});
            //printf("%i-\n",i+1);for(int j=0;j<komp.size();j++){printf("%i: ",j);for(auto k:komp[j]) printf("%i ",k+1);printf("\n");}
            continue;
        }
        int l=0,r=(int)komp.size()-1,ind=0;
        while(l<=r){
            int mid=l+r>>1;
            for(int j=0;j<n;j++) temp[j]=0;
            for(int j=0;j<=mid;j++) for(auto k:komp[j]) temp[k]=1;
            int y=Query(temp);
            temp[i]=1;
            int y1=Query(temp);
            if(y1<=y) ind=mid,r=mid-1;
            else l=mid+1;
        }
        int ind1=-1;
        if(x1<x){
            l=0,r=(int)komp.size()-1;
            while(l<=r){
                int mid=l+r>>1;
                for(int j=0;j<n;j++) temp[j]=0;
                for(int j=0;j<=mid;j++) for(auto k:komp[j]) temp[k]=1;
                int y=Query(temp);
                temp[i]=1;
                int y1=Query(temp);
                if(y1<y) ind1=mid,r=mid-1;
                else l=mid+1;
            }
        }
        for(int j=0;j<n;j++) temp[j]=0;
        temp[i]=temp[komp[ind][0]]=1;
        if(Query(temp)==1) reverse(komp[ind].begin(),komp[ind].end());
        komp[ind].pb(i);
        if(ind1!=-1){
            for(int j=0;j<n;j++) temp[j]=0;
            temp[i]=temp[komp[ind1][0]]=1;
            if(Query(temp)==2) reverse(komp[ind1].begin(),komp[ind1].end());
            for(auto j:komp[ind1]) komp[ind].pb(j);
            for(int j=ind1;j+1<komp.size();j++) komp[j]=komp[j+1];
            komp.pop_back();
        }
        //printf("%i-\n",i+1);for(int j=0;j<komp.size();j++){printf("%i: ",j);for(auto k:komp[j]) printf("%i ",k+1);printf("\n");}
	}
	vector<int> res=komp[0];
	for(auto &i:res) i++;
	Answer(res);
}

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