QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#590512#8066. Bombardmentnickbelov#RE 519ms38132kbC++203.3kb2024-09-26 01:18:082024-09-26 01:18:09

Judging History

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

  • [2024-09-26 01:18:09]
  • 评测
  • 测评结果:RE
  • 用时:519ms
  • 内存:38132kb
  • [2024-09-26 01:18:08]
  • 提交

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++,mx = max(cur,mx);
            else cur--;
        }

        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();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3600kb

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: 3596kb

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: 3500kb

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: 3600kb

input:

6 3
5 -2 5 0 1 2

output:

2
2 -5 

result:

ok 2 lines

Test #5:

score: 0
Accepted
time: 519ms
memory: 38132kb

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: 3544kb

input:

1 1
0

output:

1
-1 

result:

ok 2 lines

Test #7:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

2 1
-1 1

output:

1
0 

result:

ok 2 lines

Test #8:

score: 0
Accepted
time: 0ms
memory: 3504kb

input:

2 1
1 -1

output:

1
0 

result:

ok 2 lines

Test #9:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

2 2
1 -1

output:

1
-1 

result:

ok 2 lines

Test #10:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

1 5000001
-100000000

output:

1
-105000001 

result:

ok 2 lines

Test #11:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

1 100000000
100000000

output:

1
0 

result:

ok 2 lines

Test #12:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

2 5000000
-100000000 100000000

output:

2
-105000000 95000000 

result:

ok 2 lines

Test #13:

score: 0
Accepted
time: 0ms
memory: 3480kb

input:

2 100000000
-100000000 100000000

output:

1
0 

result:

ok 2 lines

Test #14:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

2 99999999
-100000000 100000000

output:

2
-199999999 1 

result:

ok 2 lines

Test #15:

score: 0
Accepted
time: 0ms
memory: 3760kb

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...

output:


result: