#include "library.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define per(i, a, b) for (int i = b - 1; i >= (a); --i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define umap unordered_map
#define uset unordered_set
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;
const int INF = 1000000007;
vi dummy;
int book = 0;
uset<int> queried;
int binsearch(vi books) {
vi qvec = dummy;
qvec[book] = 1;
if (sz(books) == 1) {
qvec[books[0]] = 1;
if (Query(qvec) != 1)
return -1;
else
return books[0];
}
int take = sz(books) >> 1;
rep(i, 0, take) qvec[books[i]] = 1;
int moves = Query(qvec);
qvec[book] = 0;
vi nbooks;
if (Query(qvec) < moves)
rep(i, take, sz(books)) nbooks.push_back(books[i]);
else
rep(i, 0, take) nbooks.push_back(books[i]);
return binsearch(nbooks);
}
void Solve(int n) {
dummy.resize(n);
vi ans(n);
int rgt[n];
memset(rgt, -1, sizeof(rgt));
while (book != -1 && sz(queried) + 1 != n) {
queried.insert(book);
vi vec;
rep(i, 0, n) if (!queried.count(i)) vec.push_back(i);
int next = binsearch(vec);
rgt[book] = next;
book = next;
}
book = 0;
while (true) {
queried.insert(book);
vi vec;
rep(i, 0, n) if (!queried.count(i)) vec.push_back(i);
if(vec.empty())break;
int next = binsearch(vec);
rgt[next] = book;
book = next;
}
int cnt = 0;
rep(i, 0, n) {
ans[i] = book + 1;
book = rgt[book];
if(book==-1)++cnt;
}
Answer(ans);
}
Compilation message
library.cpp: In function 'int binsearch(vi)':
library.cpp:7:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
7 | #define rep(i, a, b) for (int i = a; i < (b); ++i)
| ^
library.cpp:52:9: note: in expansion of macro 'rep'
52 | rep(i, take, sz(books)) nbooks.push_back(books[i]);
| ^~~
library.cpp: In function 'void Solve(int)':
library.cpp:66:42: warning: comparison of integer expressions of different signedness: 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
66 | while (book != -1 && sz(queried) + 1 != n) {
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
48 ms |
304 KB |
# of queries: 2586 |
| 2 |
Correct |
45 ms |
200 KB |
# of queries: 2591 |
| 3 |
Correct |
48 ms |
200 KB |
# of queries: 2726 |
| 4 |
Correct |
43 ms |
312 KB |
# of queries: 2724 |
| 5 |
Correct |
45 ms |
200 KB |
# of queries: 2708 |
| 6 |
Correct |
48 ms |
316 KB |
# of queries: 2714 |
| 7 |
Correct |
58 ms |
296 KB |
# of queries: 2716 |
| 8 |
Correct |
37 ms |
200 KB |
# of queries: 2611 |
| 9 |
Correct |
48 ms |
428 KB |
# of queries: 2709 |
| 10 |
Correct |
20 ms |
200 KB |
# of queries: 1601 |
| 11 |
Correct |
1 ms |
200 KB |
# of queries: 0 |
| 12 |
Correct |
1 ms |
200 KB |
# of queries: 2 |
| 13 |
Correct |
1 ms |
200 KB |
# of queries: 5 |
| 14 |
Runtime error |
1 ms |
328 KB |
Execution killed with signal 6 |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
48 ms |
304 KB |
# of queries: 2586 |
| 2 |
Correct |
45 ms |
200 KB |
# of queries: 2591 |
| 3 |
Correct |
48 ms |
200 KB |
# of queries: 2726 |
| 4 |
Correct |
43 ms |
312 KB |
# of queries: 2724 |
| 5 |
Correct |
45 ms |
200 KB |
# of queries: 2708 |
| 6 |
Correct |
48 ms |
316 KB |
# of queries: 2714 |
| 7 |
Correct |
58 ms |
296 KB |
# of queries: 2716 |
| 8 |
Correct |
37 ms |
200 KB |
# of queries: 2611 |
| 9 |
Correct |
48 ms |
428 KB |
# of queries: 2709 |
| 10 |
Correct |
20 ms |
200 KB |
# of queries: 1601 |
| 11 |
Correct |
1 ms |
200 KB |
# of queries: 0 |
| 12 |
Correct |
1 ms |
200 KB |
# of queries: 2 |
| 13 |
Correct |
1 ms |
200 KB |
# of queries: 5 |
| 14 |
Runtime error |
1 ms |
328 KB |
Execution killed with signal 6 |
| 15 |
Halted |
0 ms |
0 KB |
- |
