Submission #693308

# Submission time Handle Problem Language Result Execution time Memory
693308 2023-02-02T16:26:07 Z jeroenodb Library (JOI18_library) C++17
100 / 100
176 ms 628 KB
#include "library.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
int n;
int vquery(vi v) {
	vi res(n);
	for(auto i : v) res[i]=1;
	return Query(res);
}
void Solve(int N)
{
	
	n=N;
	vi special(n);
	{
	int num=0;
	for(int i=0;i<n;++i) {
		special[i]=1;
		num++;
		if(Query(special)!=num) {
			special[i]=0;
			num--;
		}
	}
	}
	vvi comps;
	for(int i=0;i<n;++i) if(special[i]) {
		comps.push_back({i});
	}
	auto merge = [&](vi old, vi nw) {
		if(vquery({old[0],nw[0]})!=1) {
			reverse(all(old));
		}
		reverse(all(nw));
		nw.insert(nw.end(),all(old));
		return nw;
	};

	auto addCmp = [&]( vi cmp) {
		auto check = [&](int i) {
			vi res(n);
			for(auto& v : cmp) res[v]=1;
			for(int j=0;j<=i;++j) {
				for(auto v : comps[j]) res[v]=1;
			}
			return Query(res);
		};
		if(check(comps.size()-1)>comps.size()) {
			return cmp;
		}
		int l = 0, r = comps.size()-1;
		while(l<r) {
			int mid = (l+r)/2;
			// check prefix, what then?
			// if found component, check on which side
			// merge it.
			// remove this component for now,
			// add it back.
			if(check(mid)>mid+1) {
				l = mid+1;
			} else {
				r = mid;
			}
		}
		// found place to insert
		auto old = comps[l];
		comps.erase(comps.begin()+l);
		return merge(old,cmp);
	};
	for(int i=0;i<n;++i) if(!special[i]) {
		vi cmp = {i};
		// find where it belongs
		cmp = addCmp(cmp);
		cmp = addCmp(cmp);
		comps.push_back(cmp);
	}
	assert(comps.size()==1);
	for(auto& i : comps[0]) ++i;
	Answer(comps[0]);
}

Compilation message

library.cpp: In lambda function:
library.cpp:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   if(check(comps.size()-1)>comps.size()) {
      |      ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 18 ms 208 KB # of queries: 1597
2 Correct 19 ms 288 KB # of queries: 1579
3 Correct 21 ms 292 KB # of queries: 1677
4 Correct 22 ms 336 KB # of queries: 1658
5 Correct 31 ms 284 KB # of queries: 1660
6 Correct 28 ms 296 KB # of queries: 1665
7 Correct 20 ms 288 KB # of queries: 1666
8 Correct 18 ms 288 KB # of queries: 1593
9 Correct 17 ms 208 KB # of queries: 1650
10 Correct 14 ms 288 KB # of queries: 995
11 Correct 0 ms 208 KB # of queries: 1
12 Correct 1 ms 212 KB # of queries: 5
13 Correct 1 ms 208 KB # of queries: 9
14 Correct 1 ms 208 KB # of queries: 12
15 Correct 1 ms 208 KB # of queries: 73
16 Correct 2 ms 300 KB # of queries: 152
# Verdict Execution time Memory Grader output
1 Correct 18 ms 208 KB # of queries: 1597
2 Correct 19 ms 288 KB # of queries: 1579
3 Correct 21 ms 292 KB # of queries: 1677
4 Correct 22 ms 336 KB # of queries: 1658
5 Correct 31 ms 284 KB # of queries: 1660
6 Correct 28 ms 296 KB # of queries: 1665
7 Correct 20 ms 288 KB # of queries: 1666
8 Correct 18 ms 288 KB # of queries: 1593
9 Correct 17 ms 208 KB # of queries: 1650
10 Correct 14 ms 288 KB # of queries: 995
11 Correct 0 ms 208 KB # of queries: 1
12 Correct 1 ms 212 KB # of queries: 5
13 Correct 1 ms 208 KB # of queries: 9
14 Correct 1 ms 208 KB # of queries: 12
15 Correct 1 ms 208 KB # of queries: 73
16 Correct 2 ms 300 KB # of queries: 152
17 Correct 176 ms 320 KB # of queries: 10618
18 Correct 171 ms 320 KB # of queries: 10484
19 Correct 162 ms 440 KB # of queries: 10621
20 Correct 152 ms 316 KB # of queries: 9949
21 Correct 172 ms 316 KB # of queries: 9335
22 Correct 156 ms 332 KB # of queries: 10639
23 Correct 121 ms 316 KB # of queries: 10651
24 Correct 59 ms 296 KB # of queries: 4956
25 Correct 147 ms 312 KB # of queries: 10380
26 Correct 156 ms 428 KB # of queries: 9719
27 Correct 68 ms 312 KB # of queries: 4961
28 Correct 157 ms 628 KB # of queries: 10479
29 Correct 123 ms 400 KB # of queries: 10475
30 Correct 152 ms 448 KB # of queries: 10479