제출 #415494

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
415494		qwerasdfzxcl	도서관 (JOI18_library)	C++14	100 / 100	609 ms	472 KiB

library

#include <bits/stdc++.h>
#include "library.h"
using namespace std;
struct node{
    vector<int> a;
    int l, r;
};
vector<node> v;
vector<int> M;

void combine(int x){
    fill(M.begin(), M.end(), 0);
    M[v[0].r-1] = M[v[x].l-1] = 1;
    int tmp = Query(M);
    if (tmp==1){
        v[0].a.push_back(v[x].l);
        v[0].r = v[x].l;
        v.erase(v.begin()+x);
    }
    else{
        v[0].a.insert(v[0].a.begin(), v[x].l);
        v[0].l = v[x].l;
        v.erase(v.begin()+x);
    }
}

int bi_search(int l, int r){
    if (r-l==1) return l;
    int m = (l+r)>>1;
    fill(M.begin(), M.end(), 0);
    for (auto &x:v[0].a) M[x-1] = 1;
    for (int i=l;i<m;i++){
        for (auto &x:v[i].a) M[x-1] = 1;
    }
    int val1 = Query(M);
    for (auto &x:v[0].a) M[x-1] = 0;
    int val2 = Query(M);
    if (val1-val2==1) return bi_search(m, r);
    return bi_search(l, m);
}

void Solve(int N){
    v.resize(N);
    M.resize(N, 0);
    for (int i=0;i<N;i++){
        v[i].a.push_back(i+1);
        v[i].l = v[i].r = i+1;
    }
    for (int i=N;i>1;i--){
        int tmp = bi_search(1, i);
        combine(tmp);
    }
    Answer(v[0].a);
}

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