QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#590518 | #8066. Bombardment | nickbelov# | RE | 513ms | 38680kb | C++20 | 3.3kb | 2024-09-26 01:24:53 | 2024-09-26 01:24:54 |
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>;
constexpr ll NN = 2e5, M = 1000000007, L = 20;
ll f1[NN], f2[NN];
ll inv(ll a, ll b=M) { return 1 < a ? b - inv(b % a, a) * b / a : 1; } // inv a mod b
ll choose(ll n, ll k) { return f1[n] * f2[k] % M * f2[n - k] % M; } // n choose k
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;
};
while(not v.empty()){
vector<Event> sweep;
for(ll x : v){
sweep.push_back({x-R,open});
sweep.push_back({x+R+1,close});
} ranges::sort(sweep,cmp);
ll mx = 0;
for(ll cur = 0; auto [time,type] : sweep){
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) cur++;
else cur--;
if(cur==mx){
bomb_spot=time;break;
}
}
// assert(bomb_spot not_eq -(ll)1e9);
ans.push_back(bomb_spot);
vll nv;
ranges::copy_if(v,back_inserter(nv),[&](ll spot){
return abs(spot-bomb_spot)>R;
});
v=nv;
}
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();
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3696kb
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: 3544kb
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: 3572kb
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: 3700kb
input:
6 3 5 -2 5 0 1 2
output:
2 2 -5
result:
ok 2 lines
Test #5:
score: 0
Accepted
time: 513ms
memory: 38680kb
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: 3572kb
input:
1 1 0
output:
1 -1
result:
ok 2 lines
Test #7:
score: 0
Accepted
time: 0ms
memory: 3416kb
input:
2 1 -1 1
output:
1 0
result:
ok 2 lines
Test #8:
score: 0
Accepted
time: 0ms
memory: 3416kb
input:
2 1 1 -1
output:
1 0
result:
ok 2 lines
Test #9:
score: 0
Accepted
time: 0ms
memory: 3404kb
input:
2 2 1 -1
output:
1 -1
result:
ok 2 lines
Test #10:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
1 5000001 -100000000
output:
1 -105000001
result:
ok 2 lines
Test #11:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
1 100000000 100000000
output:
1 0
result:
ok 2 lines
Test #12:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
2 5000000 -100000000 100000000
output:
2 -105000000 95000000
result:
ok 2 lines
Test #13:
score: 0
Accepted
time: 0ms
memory: 3408kb
input:
2 100000000 -100000000 100000000
output:
1 0
result:
ok 2 lines
Test #14:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
2 99999999 -100000000 100000000
output:
2 -199999999 1
result:
ok 2 lines
Test #15:
score: 0
Accepted
time: 0ms
memory: 3412kb
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...