oj.uz

Submission #582008

# Submission time Handle Problem Language Result Execution time Memory
582008 2022-06-23T09:27:03 Z MrDeboo Library (JOI18_library) C++17
0 / 100
 80 ms 336 KB 
#include <cstdio>
#include <vector>
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
vector<pair<int,int>>vec;
int N,L,R,n;
int Slv(int x){
	vector<int>vct[n];
	for(auto &i:vec){
		if(i.first>=L&&i.second<=R){
			vct[i.first].push_back(i.second);
			vct[i.second].push_back(i.first);
		}
	}
	int ans=0;
	vector<int>bl(n);
	for(int i=0;i<n;i++){
		if(bl[i]||vct[i].empty())continue;
		int cnt=0;
		deque<int>dq={i};
		while(dq.size()){
			int a=dq.front();
			dq.pop_front();
			if(bl[a])continue;
			bl[a]=1;
			cnt++;
			for(auto &w:vct[a])dq.push_back(w);
		}
		ans++;
	}
	x-=ans;
	int cnt=0;
	for(int i=L;i<=R;i++){
		if(!bl[i])cnt++;
	}
	return (x!=cnt);
}
int Range(int l,int r){
	vector<int>v(n);
	for(int w=l;w<=r;w++)v[w]=1;
	L=l;
	R=r;
	return Slv(Query(v));
}
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)){
					r=mid-1;
					f=mid;
				}else l=mid+1;
			}
			if(f==0)break;
			l=i;r=f-1;
			int g=0;
			while(l<=r){
				mid=(l+r)/2;
				if(Range(mid,f)){
					l=mid+1;
					g=mid;
				}else r=mid-1;
			}
			vec.push_back({g,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);
	}
	int sui=0;
	for(auto &i:vct){
		sui+=(i.size()!=0);
	}
	assert(sui>n/2);
	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+1);
		for(auto &i:vct[a])dq.push_back(i);
	}
	Answer(res);
}
// 0 0      0 1 1 0

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 308 KB # of queries: 2798
2 Correct 60 ms 308 KB # of queries: 2794
3 Correct 63 ms 312 KB # of queries: 2939
4 Correct 68 ms 308 KB # of queries: 2915
5 Correct 59 ms 308 KB # of queries: 2951
6 Correct 80 ms 296 KB # of queries: 2911
7 Correct 75 ms 312 KB # of queries: 2935
8 Correct 65 ms 312 KB # of queries: 2788
9 Correct 68 ms 304 KB # of queries: 2915
10 Correct 36 ms 208 KB # of queries: 1720
11 Runtime error 1 ms 336 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 308 KB # of queries: 2798
2 Correct 60 ms 308 KB # of queries: 2794
3 Correct 63 ms 312 KB # of queries: 2939
4 Correct 68 ms 308 KB # of queries: 2915
5 Correct 59 ms 308 KB # of queries: 2951
6 Correct 80 ms 296 KB # of queries: 2911
7 Correct 75 ms 312 KB # of queries: 2935
8 Correct 65 ms 312 KB # of queries: 2788
9 Correct 68 ms 304 KB # of queries: 2915
10 Correct 36 ms 208 KB # of queries: 1720
11 Runtime error 1 ms 336 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -