Editorial for Bedao Mini Contest 12 - MODSORT
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
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"; } }
Comments