제출 #1345407

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1345407		PieArmy	도서관 (JOI18_library)	C++20	100 / 100	86 ms	516 KiB

library

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)
#include "library.h"
mt19937 rng(chrono::high_resolution_clock().now().time_since_epoch().count());

int n;
pair<int,int>arr[1023];

void split(vector<int>v,vector<int>&a,vector<int>&b){
	shuffle(v.begin(),v.end(),rng);
	random_shuffle(v.begin(),v.end());
	for(int i=0;i<v.size();i++){
		if(i*2<v.size())a.pb(v[i]);
		else b.pb(v[i]);
	}
}

vector<int>sorucu;

void sil(){
	sorucu.clear();
	sorucu.resize(n,0);
}

void add(vector<int>v){
	for(int x:v){
		sorucu[x]=1;
	}
}

int query(){
	return Query(sorucu);
}

void connect(int x,int y){
	arr[x].fr=y;
	swap(arr[x].fr,arr[x].sc);
	arr[y].fr=x;
	swap(arr[y].fr,arr[y].sc);
}

void comb(vector<int>a,vector<int>b){
	sil();
	add(b);
	add({a[0]});
	if(query()==1){
		sil();
		add({a[0]});
		add({b[0]});
		if(query()==1){
			connect(a[0],b[0]);
		}
		else{
			connect(a[0],b.back());
		}
	}
	else{
		sil();
		add({a.back()});
		add({b[0]});
		if(query()==1){
			connect(a.back(),b[0]);
		}
		else{
			connect(a.back(),b.back());
		}
	}
}

vector<vector<int>> f(vector<int>v,int val){
	if(v.size()==1)return {v};
	vector<vector<int>>a,b;
	{
		int x,y;
		vector<int>A,B;
		split(v,A,B);
		sil();
		add(A);
		x=query();
		sil();
		add(B);
		y=query();
		a=f(A,x);
		b=f(B,y);
		val=x+y-val;
	}
	/*for(auto x:a){
		for(auto y:x){
			cerr<<y+1<<",";
		}
		cerr<<" ";
	}
	cerr<<" - ";
	for(auto x:b){
		for(auto y:x){
			cerr<<y+1<<",";
		}
		cerr<<" ";
	}
	cerr<<endl;*/
	if(a.size()>b.size())swap(a,b);
	vector<vector<int>>res;
	for(auto x:a){
		sil();
		for(auto y:b){
			add(y);
		}
		add(x);
		int k=query();
		k=b.size()+1-k;
		if(k==0)continue;
		int l=0,r=b.size()-1;
		while(l<r){
			int mi=(l+r)/2;
			sil();
			add(x);
			for(int i=0;i<=mi;i++){
				add(b[i]);
			}
			int k2=query();
			k2=mi+1+1-k2;
			if(k2!=k)l=mi+1;
			else r=mi;
		}
		comb(x,b[l]);
		if(k==1)continue;
		l=0;r=b.size()-1;
		while(l<r){
			int mi=(l+r)/2;
			sil();
			add(x);
			for(int i=0;i<=mi;i++){
				add(b[i]);
			}
			int k2=query();
			k2=mi+1+1-k2;
			if(k2==0)l=mi+1;
			else r=mi;
		}
		comb(x,b[l]);
	}
	vector<int>vis(n,0);
	for(int i=0;i<a.size();i++){
		int pos=a[i][0];
		if(vis[pos])continue;
		int las=pos;
		int k=0;
		res.pb(vector<int>(0));
		while(true){
			vis[pos]=1;
			if(k)res.back().pb(pos);
			if(arr[pos].fr!=las&&arr[pos].fr!=-1){
				las=pos;
				pos=arr[pos].fr;
				continue;
			}
			if(arr[pos].sc!=las&&arr[pos].sc!=-1){
				las=pos;
				pos=arr[pos].sc;
				continue;
			}
			if(k==1)break;
			k=1;
			las=pos;
		}
	}
	for(int i=0;i<b.size();i++){
		int pos=b[i][0];
		if(vis[pos])continue;
		res.pb(b[i]);
	}
	return res;
}

void Solve(int N){
	//srand(4);
	n=N;
	vector<int>v(n);
	for(int i=0;i<n;i++){
		v[i]=i;
		arr[i]={-1,-1};
	}
	v=f(v,1)[0];
	for(int &x:v){
		x++;
		//cerr<<x<<" ";
	}
	Answer(v);
}

컴파일 시 표준 에러 (stderr) 메시지

library.cpp: In function 'void split(std::vector<int>, std::vector<int>&, std::vector<int>&)':
library.cpp:17:23: warning: 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<int*, vector<int> >]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
   17 |         random_shuffle(v.begin(),v.end());
      |         ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from library.cpp:1:
/usr/include/c++/13/bits/stl_algo.h:4581:5: note: declared here
 4581 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:60:
In static member function 'static constexpr _Up* std::__copy_move<_IsMove, true, std::random_access_iterator_tag>::__copy_m(_Tp*, _Tp*, _Up*) [with _Tp = const int; _Up = int; bool _IsMove = false]',
    inlined from 'constexpr _OI std::__copy_move_a2(_II, _II, _OI) [with bool _IsMove = false; _II = const int*; _OI = int*]' at /usr/include/c++/13/bits/stl_algobase.h:506:30,
    inlined from 'constexpr _OI std::__copy_move_a1(_II, _II, _OI) [with bool _IsMove = false; _II = const int*; _OI = int*]' at /usr/include/c++/13/bits/stl_algobase.h:533:42,
    inlined from 'constexpr _OI std::__copy_move_a(_II, _II, _OI) [with bool _IsMove = false; _II = __gnu_cxx::__normal_iterator<const int*, vector<int> >; _OI = int*]' at /usr/include/c++/13/bits/stl_algobase.h:540:31,
    inlined from 'constexpr _OI std::copy(_II, _II, _OI) [with _II = __gnu_cxx::__normal_iterator<const int*, vector<int> >; _OI = int*]' at /usr/include/c++/13/bits/stl_algobase.h:633:7,
    inlined from 'static _ForwardIterator std::__uninitialized_copy<true>::__uninit_copy(_InputIterator, _InputIterator, _ForwardIterator) [with _InputIterator = __gnu_cxx::__normal_iterator<const int*, std::vector<int> >; _ForwardIterator = int*]' at /usr/include/c++/13/bits/stl_uninitialized.h:147:27,
    inlined from '_ForwardIterator std::uninitialized_copy(_InputIterator, _InputIterator, _ForwardIterator) [with _InputIterator = __gnu_cxx::__normal_iterator<const int*, vector<int> >; _ForwardIterator = int*]' at /usr/include/c++/13/bits/stl_uninitialized.h:185:15,
    inlined from 'constexpr _ForwardIterator std::__uninitialized_copy_a(_InputIterator, _InputIterator, _ForwardIterator, allocator<_Tp>&) [with _InputIterator = __gnu_cxx::__normal_iterator<const int*, vector<int> >; _ForwardIterator = int*; _Tp = int]' at /usr/include/c++/13/bits/stl_uninitialized.h:373:37,
    inlined from 'constexpr std::vector<_Tp, _Alloc>::vector(const std::vector<_Tp, _Alloc>&) [with _Tp = int; _Alloc = std::allocator<int>]' at /usr/include/c++/13/bits/stl_vector.h:606:31,
    inlined from 'std::vector<std::vector<int> > f(std::vector<int>, int)' at library.cpp:179:1:
/usr/include/c++/13/bits/stl_algobase.h:437:30: warning: 'void* __builtin_memmove(void*, const void*, long unsigned int)' writing between 5 and 9223372036854775807 bytes into a region of size 4 overflows the destination [-Wstringop-overflow=]
  437 |             __builtin_memmove(__result, __first, sizeof(_Tp) * _Num);
      |             ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/c++allocator.h:33,
                 from /usr/include/c++/13/bits/allocator.h:46,
                 from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52:
In member function '_Tp* std::__new_allocator<_Tp>::allocate(size_type, const void*) [with _Tp = int]',
    inlined from 'constexpr _Tp* std::allocator< <template-parameter-1-1> >::allocate(std::size_t) [with _Tp = int]' at /usr/include/c++/13/bits/allocator.h:198:40,
    inlined from 'static constexpr _Tp* std::allocator_traits<std::allocator<_CharT> >::allocate(allocator_type&, size_type) [with _Tp = int]' at /usr/include/c++/13/bits/alloc_traits.h:482:28,
    inlined from 'constexpr std::_Vector_base<_Tp, _Alloc>::pointer std::_Vector_base<_Tp, _Alloc>::_M_allocate(std::size_t) [with _Tp = int; _Alloc = std::allocator<int>]' at /usr/include/c++/13/bits/stl_vector.h:381:33,
    inlined from 'constexpr std::_Vector_base<_Tp, _Alloc>::pointer std::_Vector_base<_Tp, _Alloc>::_M_allocate(std::size_t) [with _Tp = int; _Alloc = std::allocator<int>]' at /usr/include/c++/13/bits/stl_vector.h:378:7,
    inlined from 'constexpr void std::_Vector_base<_Tp, _Alloc>::_M_create_storage(std::size_t) [with _Tp = int; _Alloc = std::allocator<int>]' at /usr/include/c++/13/bits/stl_vector.h:398:44,
    inlined from 'constexpr std::_Vector_base<_Tp, _Alloc>::_Vector_base(std::size_t, const allocator_type&) [with _Tp = int; _Alloc = std::allocator<int>]' at /usr/include/c++/13/bits/stl_vector.h:335:26,
    inlined from 'constexpr std::vector<_Tp, _Alloc>::vector(const std::vector<_Tp, _Alloc>&) [with _Tp = int; _Alloc = std::allocator<int>]' at /usr/include/c++/13/bits/stl_vector.h:603:61,
    inlined from 'std::vector<std::vector<int> > f(std::vector<int>, int)' at library.cpp:179:1:
/usr/include/c++/13/bits/new_allocator.h:151:55: note: destination object of size 4 allocated by 'operator new'
  151 |         return static_cast<_Tp*>(_GLIBCXX_OPERATOR_NEW(__n * sizeof(_Tp)));
      |                                                       ^

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