QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#590526 | #8066. Bombardment | nickbelov# | RE | 1100ms | 46720kb | C++20 | 3.5kb | 2024-09-26 01:34:18 | 2024-09-26 01:34:19 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
ostream_iterator<T> oit(const string &s = " "){ return ostream_iterator<T>(cout,s.c_str()); }
inline auto rep(int l, int r) { return views::iota(min(l, r), r); }
inline auto rep(int n) { return rep(0, n); }
inline auto rep1(int l, int r) { return rep(l, r + 1); }
inline auto rep1(int n) { return rep(1, n + 1); }
inline auto per(int l, int r) { return rep(l, r) | views::reverse; }
inline auto per(int n) { return per(0, n); }
inline auto per1(int l, int r) { return per(l, r + 1); }
inline auto per1(int n) { return per(1, n + 1); }
#define A(a) begin(a),end(a)
inline auto len = ranges::ssize;
struct chash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template<typename T, typename U> using pb_map = gp_hash_table<T, U, chash>;
template<typename T> using pb_set = gp_hash_table<T, null_type, chash>;
#define K first
#define V second
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vii = vector<vector<int>>;
typedef vector<ll> vll;
using pll = pair<ll,ll>;
using pii = pair<int,int>;
void run()
{
enum Day{
open,close
};
ll n,R; cin >> n >> R;
vll ans;
vll v(n);for(ll &x : v) cin >> x;
// ranges::sort(v);
// auto u = ranges::unique(v);
// v.erase(A(u));
struct Event{
ll time,type;
};
auto cmp = [](Event a,Event b){
if(a.time == b.time) return a.type==close;
return a.time<b.time;
};
set<ll> del;
vector<Event> sweep;
for(ll x : v){
sweep.push_back({x-R,open});
sweep.push_back({x+R+1,close});
} ranges::sort(sweep,cmp);
while(not v.empty()){
ll mx = 0;
for(ll cur = 0; auto [time,type] : sweep){
if(type==open and del.contains(time+R)) continue;
if(type==close and del.contains(time-R-1)) continue;
if(type==open) cur++;
else cur--;
mx = max(cur,mx);
}
ll bomb_spot = -(ll)1e9;
for(ll cur = 0; auto [time,type] : sweep){
if(type==open and del.contains(time+R)) continue;
if(type==close and del.contains(time-R-1)) continue;
if(type==open) cur++;
else cur--;
if(cur==mx){
bomb_spot=time;break;
}
}
assert(bomb_spot not_eq -(ll)1e9);
assert(mx);
ans.push_back(bomb_spot);
auto good = [&](ll spot){
return abs(spot-bomb_spot)>R;
};
ranges::sort(v,[&](ll spot1,ll spot2){
return !good(spot1)<!good(spot2);
});
while(not v.empty() and !good(v.back()))
del.insert(v.back()),v.pop_back();
}
cout << len(ans) << '\n';
ranges::copy(ans,oit<ll>()),cout << '\n';
}
int main()
{
//KING OF THE WORLD...... U.W.T.B
cin.tie(0);
ios_base::sync_with_stdio(false);
run();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3532kb
input:
7 1 1 2 3 3 4 4 5
output:
3 3 0 4
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
6 1 5 -2 5 0 1 2
output:
3 1 4 -3
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
6 2 5 -2 5 0 1 2
output:
2 0 3
result:
ok 2 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
6 3 5 -2 5 0 1 2
output:
2 2 -5
result:
ok 2 lines
Test #5:
score: 0
Accepted
time: 1100ms
memory: 46720kb
input:
500000 25001 87425 164368 453013 281759 284570 187224 36997 420851 299754 449905 427728 327897 213484 414578 117919 430225 250744 108264 279365 398633 374591 449596 173533 132365 60100 123114 278 170508 116490 90071 381571 353436 302710 342319 410089 114375 345407 270822 264372 326998 345344 498062 ...
output:
10 25001 75004 125007 175010 225013 275016 325019 375022 425025 474998
result:
ok 2 lines
Test #6:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
1 1 0
output:
1 -1
result:
ok 2 lines
Test #7:
score: 0
Accepted
time: 0ms
memory: 3404kb
input:
2 1 -1 1
output:
1 0
result:
ok 2 lines
Test #8:
score: 0
Accepted
time: 0ms
memory: 3496kb
input:
2 1 1 -1
output:
1 0
result:
ok 2 lines
Test #9:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
2 2 1 -1
output:
1 -1
result:
ok 2 lines
Test #10:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
1 5000001 -100000000
output:
1 -105000001
result:
ok 2 lines
Test #11:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
1 100000000 100000000
output:
1 0
result:
ok 2 lines
Test #12:
score: 0
Accepted
time: 0ms
memory: 3408kb
input:
2 5000000 -100000000 100000000
output:
2 -105000000 95000000
result:
ok 2 lines
Test #13:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
2 100000000 -100000000 100000000
output:
1 0
result:
ok 2 lines
Test #14:
score: 0
Accepted
time: 0ms
memory: 3472kb
input:
2 99999999 -100000000 100000000
output:
2 -199999999 1
result:
ok 2 lines
Test #15:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
40 5000000 -90000000 -80000000 -30000000 90000000 50000000 20000000 -65000000 -60000000 80000000 55000000 30000000 65000000 85000000 25000000 45000000 -10000000 -15000000 -50000000 -40000000 -20000000 35000000 70000000 -35000000 -25000000 60000000 10000000 -55000000 -45000000 95000000 -70000000 0 -7...
output:
14 -95000000 -80000000 -65000000 -50000000 -35000000 -20000000 -5000000 10000000 25000000 40000000 55000000 70000000 85000000 90000000
result:
ok 2 lines
Test #16:
score: -100
Runtime Error
input:
500000 5000000 -15000000 -45000000 -25000000 -70000000 -15000000 -70000000 -70000000 85000000 95000000 -80000000 60000000 -55000000 -40000000 -70000000 -75000000 -30000000 25000000 -95000000 25000000 70000000 90000000 -70000000 60000000 -60000000 0 85000000 40000000 -35000000 70000000 -95000000 -850...