QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#590549#8066. Bombardmentnickbelov#AC ✓436ms7020kbC++202.9kb2024-09-26 03:32:162024-09-26 03:32:16

Judging History

你现在查看的是最新测评结果

  • [2024-09-26 03:32:16]
  • 评测
  • 测评结果:AC
  • 用时:436ms
  • 内存:7020kb
  • [2024-09-26 03:32:16]
  • 提交

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