| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 347236 |
2021-01-12T11:57:40 Z |
jamezzz |
Library (JOI18_library) |
C++14 |
|
44 ms |
492 KB |
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>,
rb_tree_tag, tree_order_statistics_node_update> pbds;
//less_equal for identical elements
#define fi first
#define se second
#define pb emplace_back
#define ll long long
#define INF 1023456789
#define INFll 1023456789123456789
#define all(x) x.begin(), x.end()
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
int n;
vector<int> m, ans;
pbds s;
int qry(int l, int r){
for (int i = l; i <= r; ++i){
m[*s.find_by_order(i)] = 1;
}
int res = Query(m);
for (int i = 0; i < n; ++i) m[i] = 0;
return res;
}
void Solve(int N){
n = N;
m.resize(n, 1); int ept;
for (int i = 0; i < n; ++i){
m[i] = 0;
if (Query(m) == 1){
ept = i; break;
}
m[i] = 1;
}
ans.pb(ept + 1);
for (int i = 0; i < n; ++i){
m[i] = 0;
if (ept != i) s.insert(i);
}
//printf("ept: %d\n", ept + 1);
while (s.size()){
int lo = 0, hi = s.size() - 1, mid, res;
while (lo <= hi){
mid = (lo + hi) / 2;
m[ept] = 1;
int t1 = qry(lo, mid);
int t2 = qry(lo, mid);
if (t1 == t2 + 1){
lo = mid + 1;
}
else{
hi = mid - 1;
res = mid;
}
}
ept = *s.find_by_order(res);
s.erase(ept);
ans.pb(ept + 1);
//printf("ans: %d\n", ept + 1);
}
Answer(ans);
}
Compilation message
library.cpp: In function 'void Solve(int)':
library.cpp:39:25: warning: 'ept' may be used uninitialized in this function [-Wmaybe-uninitialized]
39 | m.resize(n, 1); int ept;
| ^~~
library.cpp:68:35: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
68 | ept = *s.find_by_order(res);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
492 KB |
# of queries: 2401 |
| 2 |
Correct |
43 ms |
492 KB |
# of queries: 2437 |
| 3 |
Correct |
38 ms |
364 KB |
# of queries: 2658 |
| 4 |
Correct |
37 ms |
364 KB |
# of queries: 2597 |
| 5 |
Correct |
44 ms |
364 KB |
# of queries: 2526 |
| 6 |
Correct |
37 ms |
364 KB |
# of queries: 2565 |
| 7 |
Correct |
37 ms |
364 KB |
# of queries: 2556 |
| 8 |
Correct |
36 ms |
364 KB |
# of queries: 2424 |
| 9 |
Correct |
36 ms |
364 KB |
# of queries: 2550 |
| 10 |
Correct |
24 ms |
364 KB |
# of queries: 1488 |
| 11 |
Runtime error |
0 ms |
364 KB |
Execution killed with signal 13 (could be triggered by violating memory limits) |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
492 KB |
# of queries: 2401 |
| 2 |
Correct |
43 ms |
492 KB |
# of queries: 2437 |
| 3 |
Correct |
38 ms |
364 KB |
# of queries: 2658 |
| 4 |
Correct |
37 ms |
364 KB |
# of queries: 2597 |
| 5 |
Correct |
44 ms |
364 KB |
# of queries: 2526 |
| 6 |
Correct |
37 ms |
364 KB |
# of queries: 2565 |
| 7 |
Correct |
37 ms |
364 KB |
# of queries: 2556 |
| 8 |
Correct |
36 ms |
364 KB |
# of queries: 2424 |
| 9 |
Correct |
36 ms |
364 KB |
# of queries: 2550 |
| 10 |
Correct |
24 ms |
364 KB |
# of queries: 1488 |
| 11 |
Runtime error |
0 ms |
364 KB |
Execution killed with signal 13 (could be triggered by violating memory limits) |
| 12 |
Halted |
0 ms |
0 KB |
- |
