| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 581772 | 2022-06-23T06:04:42 Z | MrDeboo | 도서관 (JOI18_library) | C++17 | 0 ms | 0 KB |
#include <cstdio>
#include <vector>
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
int seg[10000];
int N,L,R,n;
int Slv(int l=1,int r=N,int in=1){
if(l>R||r<L)return 0;
if(l>=L&&r<=R)return seg[in];
int mid=(l+r)/2;
return slv(l,mid,in*2)+slv(mid+1,r,in*2+1);
}
int Range(int l,int r){
vector<int>v(n);
for(int w=l;w<=r;w++)v[w]=1;
L=l+1;
R=r+1;
int k=Query(v)-Slv();
return k;
}
void Upd(int in){
in+=N;
seg[in]=1;
in/=2;
while(in){
seg[in]=seg[in*2]+seg[in*2+1];
in/=2;
}
}
void Solve(int GGGG){
n=GGGG;
vector<int>vct[n];
N=exp2(ceil(log2(n)));
for(int i=0;i<n;i++){
while(vct[i].size()<2){
int l=i+1,r=n-1,mid,f=0;
while(l<=r){
mid=(l+r)/2;
if(Range(i,mid)>1){
r=mid-1;
f=mid;
}else l=mid+1;
}
l=i;r=f-1;
int g=0;
while(l<=r){
mid=(l+r)/2;
if(Range(mid,f)>1){
l=mid+1;
g=mid;
}else r=mid-1;
}
Upd(f);
vct[g].push_back(f);
vct[f].push_back(g);
}
}
vector<int>res;
deque<int>dq;
for(int i=0;i<n&&dq.empty();i++){
if(vct[i].size()==1)dq.push_back(i);
}
vector<bool>bl(n);
while(dq.size()){
int a=dq.front();
dq.pop_front();
if(bl[a])continue;
bl[a]=1;
res.push_back(a);
for(auto &i:vct[a])dq.push_back(i);
}
Answer(res);
}