Submission #1052802

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052802		HunterXD	Library (JOI18_library)	C++17	100 / 100	111 ms	1084 KiB

library

#include <bits/stdc++.h>
#include "library.h"
using namespace std;

#define f first
#define s second
#define pb push_back

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n;
vector<deque<int>> piles;

vector<int> pile_range(int l, int r){
	vector<int> res(n, 0);
	for(int i = l; i <= r; i++){
		for(auto v: piles[i]) res[v-1] = 1;
	}
	return res;
}

int query_range(int l, int r, int el){
	vector<int> check = pile_range(l, r);
	check[el-1] = 1;
	return Query(check);
}

void merge1(int l, int r, int el){	
	// 11 queries at most
	int il = l, ir = r;

	while(ir-il+1 > 1){
		int mid = (il + ir) / 2;
		int q = query_range(il, mid, el);
		
		if(q == mid-il+1) ir = mid;
		else il = mid+1;
	}

	vector<int> check(n, 0);
	check[el-1] = 1, check[piles[il].front()-1] = 1;
	int q = Query(check);

	if(q == 1) piles[il].push_front(el);
	else piles[il].push_back(el);
}

void merge2(int l, int r, int el){
	// 22 queries at most
	int il = l, ir = r;

	if(ir < il) return;

	for(int i = 9; i >= 0; i--){
		int im = il + (1 << i);
		if(im >= ir) continue;

		int q = query_range(im, ir, el);
		if(q == ir-im) il = im;
	}

	for(int i = 9; i >= 0; i--){
		int im = ir - (1 << i);
		if(im <= il) continue;

		int q = query_range(il, im, el);
		if(q == im-il) ir = im;
	}

	bool il_front = false, ir_front = false;

	vector<int> check(n, 0);
	check[el-1] = 1, check[piles[il].front()-1] = 1;

	int q = Query(check);
	if(q == 1) il_front = true;

	check = vector<int>(n, 0);
	check[el-1] = 1, check[piles[ir].front()-1] = 1;
	q = Query(check);
	if(q == 1) ir_front = true;

	if(il_front && ir_front){
		piles[il].push_front(el);
		while(!piles[ir].empty()){
			piles[il].push_front(piles[ir].front());
			piles[ir].pop_front();
		}
	}

	if(il_front && !ir_front){
		piles[il].push_front(el);
		while(!piles[ir].empty()){
			piles[il].push_front(piles[ir].back());
			piles[ir].pop_back();
		}
	}

	if(!il_front && ir_front){
		piles[il].push_back(el);
		while(!piles[ir].empty()){
			piles[il].push_back(piles[ir].front());
			piles[ir].pop_front();
		}
	}

	if(!il_front && !ir_front){
		piles[il].push_back(el);
		while(!piles[ir].empty()){
			piles[il].push_back(piles[ir].back());
			piles[ir].pop_back();
		}
	}

	piles.erase(piles.begin() + ir);
}

void Solve(int N){
	n = N;
	vector<int> elements(N), res(N);
	iota(elements.begin(), elements.end(), 1);
	// shuffle(elements.begin(), elements.end(), rng);

	piles.pb({elements[0]});

	for(int i = 1; i < N; i++){
		int el = elements[i], q, m;

		q = query_range(0, piles.size()-1, el);

		if(q == piles.size()+1){
			piles.pb({el});
			continue;
		}

		if(q == piles.size()) merge1(0, piles.size()-1, el);
		if(q == piles.size()-1) merge2(0, piles.size()-1, el);

		// cout << "Piles: " << endl;
		// for(auto v: piles){
		// 	for(auto u: v){
		// 		cout << u << " ";
		// 	}
		// 	cout << endl;
		// }
	}


	res.clear();
	for(auto v: piles){
		while(!v.empty()){
			res.pb(v.front());
			v.pop_front();
		}
	}

	// for(auto v: res){
	// 	cout << v << " ";
	// }

	Answer(res);
}

Compilation message (stderr)

library.cpp: In function 'void Solve(int)':
library.cpp:131:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::deque<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |   if(q == piles.size()+1){
      |      ~~^~~~~~~~~~~~~~~~~
library.cpp:136:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::deque<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |   if(q == piles.size()) merge1(0, piles.size()-1, el);
      |      ~~^~~~~~~~~~~~~~~
library.cpp:137:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::deque<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |   if(q == piles.size()-1) merge2(0, piles.size()-1, el);
      |      ~~^~~~~~~~~~~~~~~~~
library.cpp:127:28: warning: unused variable 'm' [-Wunused-variable]
  127 |   int el = elements[i], q, m;
      |                            ^

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