oj.uz

Submission #581773

# Submission time Handle Problem Language Result Execution time Memory
581773 2022-06-23T06:05:06 Z MrDeboo Library (JOI18_library) C++17
0 / 100
 290 ms 340 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);
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 290 ms 340 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Runtime error 290 ms 340 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -