Hướng dẫn giải của Bedao Regular Contest 03 - RACE


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: bedao

Ta sẽ chia lời giải ra làm hai phần:

1, Số lượng va chạm đã diễn ra trong cuộc thi ngay trước khi mọi chú chó cán đích:

  • Nhận xét rằng khi hai chú chó va chạm, thay vì đổi vận tốc của hai chú chó theo chiều ngược lại, chúng ta có thể xem rằng hai chú chó vẫn giữ nguyên vận tốc, nhưng ID của hai chú chó thay đổi.

  • Khi đó bài toán trở thành cho một số đường chéo đi lên, và một số đường chéo đi xuống, đếm số cặp đường chéo giao nhau.

  • Chúng ta sort các đường chéo đi lên theo thứ tự tăng dần. Khi đó, với mỗi đường chéo đi xuống, ta có thể sử dụng thuật toán chặt nhị phân (hoặc hai con trỏ nếu sort cả các đường chéo xuống) để đếm xem có bao nhiêu đường chéo lên đã cắt.

  • Ngoài ra, còn một cách khác để giải đó là nếu ta lấy mảng tọa độ vị trí cuối cùng, nhưng ID của mỗi chú chó không thay đổi qua va chạm. Số lượng cặp nghịch thế trên mảng này cũng chính là kết quả.

2, Tọa độ ~y_i~ là vị trí cán đích của chú chó thứ ~i~:

  • Nhận xét rằng vị trí tương đối của mỗi chú chó so với những chú chó còn lại là không thay đổi. Điều này có nghĩa rằng nếu ban đầu, chú chó thứ ~i~ đứng ở dưới cùng, thì sau khi kết thúc cuộc thi, chú chó thứ ~i~ vẫn đứng ở dưới cùng.

  • Do đó, ta sinh ra ~n~ tọa độ vị trí cuối cùng từ ~n~ tọa độ vị trí ban đầu.

  • Vì vị trí tương đối không thay đổi, ta gán ID cho từng vị trí từ dưới lên, tương tự như thứ tự ID ở mảng ban đầu.

Code mẫu

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/

#include <bits/stdc++.h>

#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pb push_back

/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/

const long double PI = 3.1415926535897932384626433832795;
const int INF = 1000000000000000000;
const int MOD = 1000000007;
const int MOD2 = 1000000009;
const long double EPS = 1e-6;

using namespace std;

int n, k;
int p[200005], t[200005], res[200005];
vector<pii> ord;
vector<int> v1, v2, pos;

signed main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);

    cin >> n >> k;
    for1(i,1,n) cin >> p[i];
    for1(i,1,n) {
        cin >> t[i];
        if (t[i] == 1) v1.push_back(p[i]);
        else v2.push_back(p[i]);
    }
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());

    for1(i,1,n) {
        ord.push_back({p[i], i});
        pos.push_back({p[i] + t[i] * k});
    }
    sort(ord.begin(), ord.end());
    sort(pos.begin(), pos.end());
    for1(i,0,n - 1) res[ord[i].second] = pos[i];

    for1(i,1,n) {
        if (t[i] == 1) {
            res[0] += upper_bound(v2.begin(), v2.end(), p[i] + 2 * k - 1) - v2.begin() - (lower_bound(v2.begin(), v2.end(), p[i]) - v2.begin());
        }
        else {
            res[0] += upper_bound(v1.begin(), v1.end(), p[i]) - v1.begin() - (lower_bound(v1.begin(), v1.end(), p[i] - 2 * k + 1) - v1.begin());
        }
    }

    cout << (res[0] >> 1) << "\n";
    for1(i,1,n) cout << res[i] << " ";

}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.