#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;
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
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 |
| # |
결과 |
실행 시간 |
메모리 |
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 |
