Hướng dẫn giải của Bedao Mini Contest 12 - MODSORT


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.

Nhận xét #1 : Điều kiện ~|a_i - a_{i+1}|~ chia hết cho ~k~ tương đương ~a_i~ và ~a_{i+1}~ đồng dư khi chia cho ~k~, vậy ta không thể thay đổi thứ tự của các phần tử nếu chúng đồng dư khi chia cho ~k~.

Nhận xét #2 : Theo thuật toán kinh điển merge sort, luôn tồn tại cách để hợp nhất ~2~ dãy không giảm thành ~1~ dãy không giảm ~(~dãy sau khi hợp nhất chứa tất cả phần tử của ~2~ dãy ban đầu và không làm thay đổi thứ tự gốc của chúng~)~

Từ ~2~ nhận xét trên, với mỗi số ~x~ thỏa mãn ~0 \leq x < k~, ta lọc ra các phần tử ~a_j~ sao cho ~a_j \equiv x \pmod{k}~ rồi kiểm tra xem liệu chúng có được xếp theo thứ tự không giảm trong dãy ~a~ ban đầu. Nếu điều kiện này đúng với mọi ~x~ ~(0 \leq x < k)~ thì đáp án là Yes, không thì đáp án là No.

Code mẫu

#include <bits/stdc++.h>

using namespace std;

#define int long long 
#define fo(i, a, b) for(int i = a; i <= b; i++)
#define _fo(i, a, b) for(int i = a; i >= b; i--)
#define foa(i, a) for (auto &i : a)
#define sz(a) ((int) a.size())
#define all(a) begin(a), end(a)
#define fi first
#define se second
#define pb(x) push_back(x)
#define mk(x, y) make_pair(x, y)

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int LOG = 22; 
const int MAX = 2e5+5;
const int MOD = 1e9+7;
const int SQRT = 400;
const ll INF = 2e9;
const ll lon = 1e18;

int n, k;
int a[MAX];
vector<pii> temp;

bool check() {
    sort(all(temp));
    fo(i, 1, n) {
        if(temp[i].fi != temp[i-1].fi) continue;
        if(a[temp[i].se] < a[temp[i-1].se]) return false;
    }
    return true;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int t;
    cin >> t;
    if(t > 100) cout << "cac\n";
    while(t--) {
        cin >> n >> k;
        fo(i, 1, n) cin >> a[i];

        temp.clear();
        temp.pb(mk(-1, -1));
        fo(i, 1, n) temp.pb(mk(a[i] % k, i)); 

        if(check()) cout << "Yes";
        else cout << "No";
        cout << "\n";
    }
}

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.