| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 954565 |
2024-03-28T07:09:13 Z |
Sharky |
Library (JOI18_library) |
C++17 |
|
189 ms |
720 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;
v.clear();
return Query(vt);
}
vector<int> adj[1001], ans;
void dfs(int u, int p = -1) {
ans.push_back(u);
for (int v : adj[u]) if (v != p) dfs(v, u);
}
void Solve(int n) {
if (n == 1) {
ans = {1};
Answer(ans);
return;
}
outn = n;
vector<int> ee;
vector<int> deg(n+1, 2), cand, vt;
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), deg[sk]--;
cand.push_back(sk);
}
int ender = ee[0], i = ee[0], o = ee[1];
while (i != o) {
int sz = cand.size();
int rt = (int) floor(sqrt(sz)), nxt;
shuffle(cand.begin(), cand.end(), g);
vector<int> er;
for (int j = 0; j < sz; j += rt) {
for (int k = j; k < min(sz, j + rt); k++) {
vt.push_back(cand[k]);
if (cand[k] == i) continue;
}
vector<int> vt2 = vt;
vt2.push_back(i);
int extra = query(vt2) - query(vt);
if (extra) continue;
for (int k = j; k < min(sz, j + rt); k++) {
if (cand[k] == i) continue;
vt.push_back(i);
vt.push_back(cand[k]);
if (query(vt) == 1) {
deg[cand[k]]--, deg[i]--;
adj[cand[k]].push_back(i);
adj[i].push_back(cand[k]);
nxt = cand[k];
if (!deg[cand[k]]) er.push_back(k);
break;
}
}
if (!deg[i]) break;
}
reverse(er.begin(), er.end());
for (auto x : er) cand.erase(cand.begin() + x);
for (int j = cand.size() - 1; j >= 0; j--) if (cand[j] == i) {
cand.erase(cand.begin() + j);
break;
}
i = nxt;
}
dfs(ender);
Answer(ans);
}
Compilation message
library.cpp: In function 'void Solve(int)':
library.cpp:79:5: warning: 'nxt' may be used uninitialized in this function [-Wmaybe-uninitialized]
79 | i = nxt;
| ~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
464 KB |
# of queries: 3872 |
| 2 |
Correct |
32 ms |
712 KB |
# of queries: 3746 |
| 3 |
Correct |
33 ms |
480 KB |
# of queries: 4035 |
| 4 |
Correct |
28 ms |
708 KB |
# of queries: 3889 |
| 5 |
Correct |
31 ms |
480 KB |
# of queries: 3990 |
| 6 |
Correct |
27 ms |
704 KB |
# of queries: 4048 |
| 7 |
Correct |
31 ms |
476 KB |
# of queries: 4160 |
| 8 |
Correct |
27 ms |
708 KB |
# of queries: 3785 |
| 9 |
Correct |
32 ms |
712 KB |
# of queries: 4044 |
| 10 |
Correct |
17 ms |
720 KB |
# of queries: 2179 |
| 11 |
Correct |
1 ms |
344 KB |
# of queries: 0 |
| 12 |
Correct |
1 ms |
344 KB |
# of queries: 5 |
| 13 |
Correct |
0 ms |
344 KB |
# of queries: 11 |
| 14 |
Correct |
0 ms |
344 KB |
# of queries: 16 |
| 15 |
Correct |
2 ms |
344 KB |
# of queries: 104 |
| 16 |
Correct |
2 ms |
344 KB |
# of queries: 221 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
464 KB |
# of queries: 3872 |
| 2 |
Correct |
32 ms |
712 KB |
# of queries: 3746 |
| 3 |
Correct |
33 ms |
480 KB |
# of queries: 4035 |
| 4 |
Correct |
28 ms |
708 KB |
# of queries: 3889 |
| 5 |
Correct |
31 ms |
480 KB |
# of queries: 3990 |
| 6 |
Correct |
27 ms |
704 KB |
# of queries: 4048 |
| 7 |
Correct |
31 ms |
476 KB |
# of queries: 4160 |
| 8 |
Correct |
27 ms |
708 KB |
# of queries: 3785 |
| 9 |
Correct |
32 ms |
712 KB |
# of queries: 4044 |
| 10 |
Correct |
17 ms |
720 KB |
# of queries: 2179 |
| 11 |
Correct |
1 ms |
344 KB |
# of queries: 0 |
| 12 |
Correct |
1 ms |
344 KB |
# of queries: 5 |
| 13 |
Correct |
0 ms |
344 KB |
# of queries: 11 |
| 14 |
Correct |
0 ms |
344 KB |
# of queries: 16 |
| 15 |
Correct |
2 ms |
344 KB |
# of queries: 104 |
| 16 |
Correct |
2 ms |
344 KB |
# of queries: 221 |
| 17 |
Runtime error |
189 ms |
720 KB |
Execution killed with signal 13 |
| 18 |
Halted |
0 ms |
0 KB |
- |
