Submission #290845

#	Time	Username	Problem	Language	Result	Execution time	Memory
290845		thebes	Library (JOI18_library)	C++14	100 / 100	232 ms	512 KiB

library

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

typedef vector<int> vi;
typedef vector<vi> vvi;
vvi arr; vi M; int i, j, lo, hi, mid;

inline bool qu(int s,int e){
    fill(M.begin(),M.end(),0);
    for(int i=s;i<=e;i++){
        for(auto v : arr[i]) M[v] = 1;
    }
    return Query(M) != e-s+1;
}

inline bool qu2(int x,int y){
    fill(M.begin(),M.end(),0);
    M[x]=M[y]=1;
    return Query(M)==1;
}

inline vi merge(vi x,vi y){
    if(qu2(x[0],y[0])){
        reverse(x.begin(),x.end());
        for(auto v : y) x.push_back(v);
        return x;
    }
    else if(qu2(x.back(),y.back())){
        reverse(y.begin(),y.end());
        for(auto v : y) x.push_back(v);
        return x;
    }
    else if(qu2(x.back(),y[0])){
        for(auto v : y) x.push_back(v);
        return x;
    }
    else{
        for(auto v : x) y.push_back(v);
        return y;
    }
}

inline void mrg(int x,int y){
    vi a, b;
    a = arr[x], b = arr[y];
    arr.erase(arr.begin()+y);
    arr.erase(arr.begin()+x);
    arr.insert(arr.begin()+y-1,merge(a,b));
}

void Solve(int N){
    arr.resize(N); M.resize(N);
	for(i=0;i<N;i++) arr[i].push_back(i);
	for(i=1;i<(int)arr.size();i++){
        while(i&&qu(0,i)){
            lo = 1, hi = i;
            while(lo<hi){
                mid = (lo+hi)>>1;
                if(qu(mid,i)) lo=mid+1;
                else hi=mid;
            }
            lo--;
            mrg(lo, i); i--;
        }
	}
	for(auto &v : arr[0]) v++;
	Answer(arr[0]);
}

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