QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#590549 | #8066. Bombardment | nickbelov# | AC ✓ | 436ms | 7020kb | C++20 | 2.9kb | 2024-09-26 03:32:16 | 2024-09-26 03:32:16 |
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()
{
ll n,R; cin >> n >> R;
vll ans;
vll v(n);for(ll &x : v) cin >> x;
while(not v.empty()){
ranges::sort(v);
pll here {-1,0};
for(int i : rep(len(v))){ //try backwords and forwards
{//forwards
auto lb = ranges::lower_bound(v,v[i]+2*R);
ll place = v[i]+R;
ll cnt = lb-(i+v.begin());
if(cnt==here.second and place<here.first) here={place,cnt};
else if(cnt>here.second) here = {place,cnt};
}
{ //backwords
auto lb = ranges::lower_bound(v,v[i]-2*R);
ll place = v[i]-R;
ll cnt = (i+v.begin())-lb+1;
if(cnt==here.second and place<here.first) here={place,cnt};
else if(cnt>here.second) here = {place,cnt};
}
}
ll place = here.first;
// cout << here.first << " " << here.second << endl;
ans.push_back(place);
erase_if(v,[&](ll x){ return abs(place-x)<=R;}); //kill it all!!!
}
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: 0ms
memory: 3808kb
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: 3776kb
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: 3608kb
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: 3584kb
input:
6 3 5 -2 5 0 1 2
output:
2 2 -5
result:
ok 2 lines
Test #5:
score: 0
Accepted
time: 324ms
memory: 6944kb
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: 3612kb
input:
1 1 0
output:
1 -1
result:
ok 2 lines
Test #7:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
2 1 -1 1
output:
1 0
result:
ok 2 lines
Test #8:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
2 1 1 -1
output:
1 0
result:
ok 2 lines
Test #9:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
2 2 1 -1
output:
1 -1
result:
ok 2 lines
Test #10:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
1 5000001 -100000000
output:
1 -105000001
result:
ok 2 lines
Test #11:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
1 100000000 100000000
output:
1 0
result:
ok 2 lines
Test #12:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
2 5000000 -100000000 100000000
output:
2 -105000000 95000000
result:
ok 2 lines
Test #13:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
2 100000000 -100000000 100000000
output:
1 0
result:
ok 2 lines
Test #14:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
2 99999999 -100000000 100000000
output:
2 -199999999 1
result:
ok 2 lines
Test #15:
score: 0
Accepted
time: 0ms
memory: 3540kb
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: 0
Accepted
time: 165ms
memory: 6916kb
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...
output:
16 -75000000 -30000000 65000000 -60000000 30000000 -90000000 45000000 80000000 -45000000 -15000000 90000000 5000000 15000000 -105000000 -10000000 50000000
result:
ok 2 lines
Test #17:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
10 572223 -2532666 -3003959 -8538825 9071942 -10475217 -3901005 -5116326 -3125580 -1195446 4299148
output:
8 -3576182 -11047440 -9111048 -5688549 -3104889 -1767669 3726925 8499719
result:
ok 2 lines
Test #18:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
100 2665309 10065248 25386613 50839193 -45145139 -15262316 -27823275 -45231498 1147086 -49534765 45305821 -47588528 -23883782 -43535631 -17224276 -987275 -22340945 -30880670 -48743202 7092883 -9574654 -12924292 9623463 21591733 -350435 -7213867 37104166 -36255841 10205742 -22739243 -24189117 -420853...
output:
20 -47187408 -15589601 494693 -25228700 7540433 38860848 -9879176 15202074 22721304 -38838401 -31449290 42640512 48861750 29261308 -23392117 -5460481 -55952996 -46200940 -15461111 1069092
result:
ok 2 lines
Test #19:
score: 0
Accepted
time: 1ms
memory: 3792kb
input:
1000 1188209 -15798452 -20691057 -3153590 -20159606 14848680 -16938349 10640744 -4068675 17373400 2680130 11336281 20227094 17552257 13134395 12162537 16815587 -20944801 6731403 -2871158 -135237 22666190 7433801 17843386 12442717 16281655 -20208717 -23405037 5082386 -5225015 -2304002 -17486204 10937...
output:
28 -2898885 376225 -14657397 -20855468 -10150263 7323694 -7452829 21873990 15472438 12905550 -17673395 18069502 4115838 -5343919 10236003 -23292424 -12623984 1630616 19256376 -20167974 22502063 -2067861 4814772 -17140062 7778890 -9974056 12962763 15627378
result:
ok 2 lines
Test #20:
score: 0
Accepted
time: 436ms
memory: 6944kb
input:
500000 460641 5675510 -4573803 -8327464 -3357448 -4273101 -7235703 7622497 4364005 4502585 2657860 -7290269 2944687 -891837 6305646 -2073735 -8426131 4813406 -8036265 -2240328 8597299 -1177542 -963866 8333780 252128 -3582986 5648572 -2254077 -4110503 -5129773 4729094 -4527295 -6377070 3271666 886364...
output:
31 5656366 -7237261 6965487 2378859 4550189 -8598359 -1010208 -5541267 1233777 -3573216 -2272952 3489489 195176 7945659 -4615203 8752150 -6462591 -8158716 6044153 -3194281 -1931492 -726238 1457531 2568130 4735013 -9519799 3628898 -4494585 312430 7024292 -5536557
result:
ok 2 lines
Test #21:
score: 0
Accepted
time: 436ms
memory: 7020kb
input:
500000 2987538 -25780772 39949495 56720924 -38638116 -39744871 50195451 59629634 -5222957 -452338 2797208 9205870 -6950069 -42033155 48782048 16099604 -30937108 10108457 -27948760 -19413368 -50414015 -43635176 -5546224 -54046681 13999933 18837139 22081878 4546040 -3524453 23660130 51859794 45418099 ...
output:
31 13671418 -54008482 55529795 -19437801 29633791 -30231092 -40007486 4527412 -6854771 -13439882 48710466 20547314 -47697273 36523399 42695441 -1448129 -25413030 -36206919 7695018 23657285 -59983703 -45983488 56763080 30547701 14572175 49553623 -12830018 -53673017 36719299 42735346 -19415465
result:
ok 2 lines
Test #22:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
40 5000000 -100000000 -29999986 -54999991 -89999998 10000022 70000034 -59999992 65000033 -64999993 -14999983 -9999982 -39999988 -49999990 75000035 20000024 50000030 -34999987 20 60000032 40000028 -84999997 -74999995 -24999985 30000026 -19999984 95000039 90000038 80000036 -79999996 45000029 25000025 ...
output:
20 -99999999 -89999997 -79999995 -69999993 -59999991 -49999989 -39999987 -29999985 -19999983 -9999981 21 10000023 20000025 30000027 40000029 50000031 60000033 70000035 80000037 90000039
result:
ok 2 lines
Test #23:
score: 0
Accepted
time: 190ms
memory: 7012kb
input:
500000 5000000 30000026 -29999986 25000025 50000030 50000030 50000030 -59999992 20000024 35000027 -69999994 15000023 -94999999 40000028 -19999984 45000029 -69999994 -14999983 -69999994 -84999997 -4999981 35000027 -4999981 30000026 -79999996 40000028 35000027 -59999992 80000036 20000024 20000024 2000...
output:
23 20000025 35000028 45000030 -69999993 -84999996 90000039 -24999984 65000034 -39999987 -99999999 -9999981 10000023 25000026 75000036 55000032 -59999991 -34999986 21 -19999983 80000037 -94999998 -79999995 -49999989
result:
ok 2 lines