oj.uz

Submission #954583

# Submission time Handle Problem Language Result Execution time Memory
954583 2024-03-28T07:38:11 Z Sharky Library (JOI18_library) C++17
100 / 100
 214 ms 1736 KB 
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
 
random_device rd;
mt19937 g(rd());
int outn, qc = 0;

void TLE() {
	TLE();
}
 
int query(vector<int> v) {
	qc++;
	if (qc > 20000) TLE();
	vector<int> vt(outn, 0);
	for (auto x : v) vt[x - 1] = 1;
	return Query(vt);
}
 
void Solve(int n) {
	vector<int> ans, ee, vt;
	if (n == 1) {
		ans = {1};
		Answer(ans);
		return;
	}
	outn = n;
	set<int> cand;
	for (int sk = 1; sk <= n; sk++) {
		for (int i = 1; i <= n; i++) if (i != sk) vt.push_back(i);
		if (query(vt) == 1) ee.push_back(sk);
		vt.clear();
		cand.insert(sk);
	}
	int i = ee[0], o = ee[1];
	ans.push_back(i);
	cand.erase(i);
	while (i != o) {
		int nxt;
		vector<int> tos; // 1000 佳麗 of tos, competing to match with i
		for (auto x : cand) tos.push_back(x);
		shuffle(tos.begin(), tos.end(), g);
		while (tos.size() > 1) {
			vector<int> l, r;
			int mid = tos.size() / 2;
			for (int i = 0; i < mid; i++) l.push_back(tos[i]);
			for (int i = mid; i < tos.size(); i++) r.push_back(tos[i]);
			vector<int> l2 = l;
			l2.push_back(i);
			if (query(l) != query(l2)) tos = r;
			else tos = l;
		}
		cand.erase(tos[0]);
		i = tos[0];
		ans.push_back(tos[0]);
	}
	Answer(ans);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:48:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |    for (int i = mid; i < tos.size(); i++) r.push_back(tos[i]);
      |                      ~~^~~~~~~~~~~~
library.cpp:40:7: warning: unused variable 'nxt' [-Wunused-variable]
   40 |   int nxt;
      |       ^~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1212 KB # of queries: 2576
2 Correct 24 ms 968 KB # of queries: 2569
3 Correct 25 ms 700 KB # of queries: 2690
4 Correct 31 ms 708 KB # of queries: 2704
5 Correct 20 ms 960 KB # of queries: 2694
6 Correct 25 ms 956 KB # of queries: 2700
7 Correct 24 ms 1480 KB # of queries: 2700
8 Correct 19 ms 1468 KB # of queries: 2585
9 Correct 26 ms 708 KB # of queries: 2691
10 Correct 15 ms 956 KB # of queries: 1589
11 Correct 1 ms 344 KB # of queries: 0
12 Correct 1 ms 344 KB # of queries: 2
13 Correct 1 ms 344 KB # of queries: 5
14 Correct 0 ms 344 KB # of queries: 10
15 Correct 1 ms 344 KB # of queries: 89
16 Correct 2 ms 452 KB # of queries: 205

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1212 KB # of queries: 2576
2 Correct 24 ms 968 KB # of queries: 2569
3 Correct 25 ms 700 KB # of queries: 2690
4 Correct 31 ms 708 KB # of queries: 2704
5 Correct 20 ms 960 KB # of queries: 2694
6 Correct 25 ms 956 KB # of queries: 2700
7 Correct 24 ms 1480 KB # of queries: 2700
8 Correct 19 ms 1468 KB # of queries: 2585
9 Correct 26 ms 708 KB # of queries: 2691
10 Correct 15 ms 956 KB # of queries: 1589
11 Correct 1 ms 344 KB # of queries: 0
12 Correct 1 ms 344 KB # of queries: 2
13 Correct 1 ms 344 KB # of queries: 5
14 Correct 0 ms 344 KB # of queries: 10
15 Correct 1 ms 344 KB # of queries: 89
16 Correct 2 ms 452 KB # of queries: 205
17 Correct 193 ms 1540 KB # of queries: 18184
18 Correct 188 ms 1484 KB # of queries: 17897
19 Correct 209 ms 968 KB # of queries: 18148
20 Correct 176 ms 1276 KB # of queries: 16972
21 Correct 177 ms 1736 KB # of queries: 15905
22 Correct 198 ms 1228 KB # of queries: 18146
23 Correct 214 ms 1492 KB # of queries: 18127
24 Correct 80 ms 1252 KB # of queries: 8331
25 Correct 189 ms 1504 KB # of queries: 17739
26 Correct 174 ms 1296 KB # of queries: 16591
27 Correct 77 ms 1532 KB # of queries: 8277
28 Correct 211 ms 1228 KB # of queries: 18144
29 Correct 182 ms 1508 KB # of queries: 18093
30 Correct 175 ms 1036 KB # of queries: 18128