oj.uz

Submission #1052802

# Submission time Handle Problem Language Result Execution time Memory
1052802 2024-08-10T23:07:01 Z HunterXD Library (JOI18_library) C++17
100 / 100
 111 ms 1084 KB 
#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

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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 344 KB # of queries: 1294
2 Correct 11 ms 600 KB # of queries: 1287
3 Correct 11 ms 344 KB # of queries: 1359
4 Correct 7 ms 344 KB # of queries: 1363
5 Correct 10 ms 476 KB # of queries: 1336
6 Correct 6 ms 344 KB # of queries: 1359
7 Correct 11 ms 344 KB # of queries: 1346
8 Correct 10 ms 344 KB # of queries: 1270
9 Correct 10 ms 488 KB # of queries: 1365
10 Correct 9 ms 344 KB # of queries: 784
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 2
13 Correct 0 ms 344 KB # of queries: 4
14 Correct 0 ms 344 KB # of queries: 6
15 Correct 1 ms 344 KB # of queries: 46
16 Correct 1 ms 344 KB # of queries: 114

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 344 KB # of queries: 1294
2 Correct 11 ms 600 KB # of queries: 1287
3 Correct 11 ms 344 KB # of queries: 1359
4 Correct 7 ms 344 KB # of queries: 1363
5 Correct 10 ms 476 KB # of queries: 1336
6 Correct 6 ms 344 KB # of queries: 1359
7 Correct 11 ms 344 KB # of queries: 1346
8 Correct 10 ms 344 KB # of queries: 1270
9 Correct 10 ms 488 KB # of queries: 1365
10 Correct 9 ms 344 KB # of queries: 784
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 2
13 Correct 0 ms 344 KB # of queries: 4
14 Correct 0 ms 344 KB # of queries: 6
15 Correct 1 ms 344 KB # of queries: 46
16 Correct 1 ms 344 KB # of queries: 114
17 Correct 89 ms 600 KB # of queries: 9040
18 Correct 111 ms 856 KB # of queries: 8969
19 Correct 79 ms 600 KB # of queries: 9001
20 Correct 75 ms 552 KB # of queries: 8450
21 Correct 75 ms 656 KB # of queries: 7966
22 Correct 91 ms 600 KB # of queries: 9113
23 Correct 100 ms 1084 KB # of queries: 9064
24 Correct 40 ms 600 KB # of queries: 4143
25 Correct 80 ms 912 KB # of queries: 8850
26 Correct 80 ms 648 KB # of queries: 8268
27 Correct 36 ms 344 KB # of queries: 4146
28 Correct 19 ms 344 KB # of queries: 1998
29 Correct 18 ms 344 KB # of queries: 1996
30 Correct 20 ms 344 KB # of queries: 1998