#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX = 2e5 + 5;
const int BLOCK = 600;
int tree[MAX];
void update(int pos, int val){
while(pos < MAX){
tree[pos] += val;
pos += pos & (-pos);
}
}
int ask(int l, int r){
if(r < l) return 0;
if(l != 1) return ask(1, r) - ask(1, l - 1);
int ans = 0;
while(r > 0){
ans += tree[r];
r -= r & (-r);
}
return ans;
}
int intRand(){
return (rand() << 14) | rand();
}
vector<int> mp[MAX];
vector<int> query(int i){
if(!mp[i].empty()) return mp[i];
return mp[i] = ask(i - 1);
}
int find_best(int n) {
vector<int> order(n);
srand(time(0));
iota(order.begin(), order.end(), 1);
random_shuffle(order.begin(), order.end());
vector<int> a;
int cnt = 0;
set<int> st;
for (int i = 0; i < n; i++)
{
st.insert(i + 1);
}
for (int j = 0; j < min(450, (int)order.size()); ++j)
{
int i = order[j];
a = query(i);
if(a[0] + a[1] == 0) return i - 1;
if(a[0] + a[1] < cnt){
update(i, 1);
st.erase(i);
}
else{
cnt = a[0] + a[1];
}
}
vector<int> blocks;
int c = 0;
while(true){
auto itr = st.lower_bound(c);
if(itr == st.end()) break;
a = query(*itr);
if(a[0] + a[1] == 0) return (*itr) - 1;
if(a[0] + a[1] < cnt){
update(*itr, 1);
st.erase(itr);
continue;
}
c = *itr;
blocks.push_back(c);
c += BLOCK;
}
if(*prev(st.end()) != blocks.back()){
blocks.push_back(*prev(st.end()));
}
for (int i = 0; i < blocks.size() - 1; i++)
{
int b1 = blocks[i], b2 = blocks[i + 1];
while(query(b1)[2] - query(b2)[2] - ask(b1, b2) != 0);
{
int l = b1, r = b2;
while(l <= r){
int x = (l + r) / 2;
auto itr = st.lower_bound(x);
if(itr == st.end() || (*itr) > r){
--itr;
}
int mid = *itr;
a = query(mid);
if(a[0] + a[1] == 0){
return mid - 1;
}
if(a[0] + a[1] < cnt && !ask(mid, mid)){
update(mid, 1);
st.erase(mid);
break;
}
a[0] -= query(b1)[0] + ask(b1, mid - 1);
a[1] -= query(b2)[1] + ask(mid + 1, b2);
if(a[1] > 0){
l = mid + 1;
}
else{
r = mid - 1;
}
}
}
}
}
Compilation message
prize.cpp: In function 'int find_best(int)':
prize.cpp:90:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for (int i = 0; i < blocks.size() - 1; i++)
| ~~^~~~~~~~~~~~~~~~~~~
prize.cpp:93:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
93 | while(query(b1)[2] - query(b2)[2] - ask(b1, b2) != 0);
| ^~~~~
prize.cpp:94:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
94 | {
| ^
prize.cpp:42:24: warning: control reaches end of non-void function [-Wreturn-type]
42 | vector<int> order(n);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
15220 KB |
Output is correct |
| 2 |
Correct |
59 ms |
15264 KB |
Output is correct |
| 3 |
Correct |
54 ms |
15228 KB |
Output is correct |
| 4 |
Correct |
69 ms |
15228 KB |
Output is correct |
| 5 |
Correct |
56 ms |
15232 KB |
Output is correct |
| 6 |
Correct |
45 ms |
15076 KB |
Output is correct |
| 7 |
Correct |
67 ms |
15220 KB |
Output is correct |
| 8 |
Correct |
53 ms |
15216 KB |
Output is correct |
| 9 |
Correct |
51 ms |
15280 KB |
Output is correct |
| 10 |
Correct |
69 ms |
15244 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
15224 KB |
Output is correct |
| 2 |
Correct |
53 ms |
15244 KB |
Output is correct |
| 3 |
Correct |
63 ms |
15456 KB |
Output is correct |
| 4 |
Correct |
70 ms |
15264 KB |
Output is correct |
| 5 |
Correct |
59 ms |
15176 KB |
Output is correct |
| 6 |
Correct |
43 ms |
15140 KB |
Output is correct |
| 7 |
Correct |
60 ms |
15212 KB |
Output is correct |
| 8 |
Correct |
55 ms |
15172 KB |
Output is correct |
| 9 |
Correct |
53 ms |
15180 KB |
Output is correct |
| 10 |
Correct |
74 ms |
15192 KB |
Output is correct |
| 11 |
Correct |
56 ms |
15384 KB |
Output is correct |
| 12 |
Correct |
43 ms |
15096 KB |
Output is correct |
| 13 |
Execution timed out |
3071 ms |
15328 KB |
Time limit exceeded |
| 14 |
Halted |
0 ms |
0 KB |
- |
