Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include "bits/stdc++.h"
- using namespace std;
- #define all(a) a.begin(), a.end()
- #define int long long
- void retract(vector<int>& a, int k) {
- int n = (int)a.size();
- map<int, vector<int>> cnt;
- for (int i = 0; i < n; i++) {
- cnt[a[i] % k].push_back(a[i]);
- }
- vector<int> b;
- for (auto& it : cnt) {
- b.push_back(it.first);
- }
- for (int i = 0; i < (int)b.size(); i++) {
- if (i + 1 < (int)b.size()) {
- if ((b[i] + b[i + 1]) % k == 0) {
- swap(b[i], b[i - 1 >= 0 ? i - 1 : (int)b.size() - 1]);
- }
- }
- }
- a.clear();
- for (int i = 0; i < (int)b.size(); i++) {
- for (int& j : cnt[b[i]]) {
- a.push_back(j);
- }
- }
- }
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- int n, k; cin >> n >> k;
- vector<int> a;
- vector<int> ost1, ost2;
- for (int i = 0; i < n; i++) {
- int x; cin >> x;
- int o = x % k;
- if (o == 0) {
- ost1.push_back(x);
- }
- else if (k % 2 == 0 && o == k / 2) {
- ost2.push_back(x);
- }
- else {
- a.push_back(x);
- }
- }
- auto cmp = [&](const int& lhs, const int& rhs) {
- return lhs % k < rhs % k;
- };
- sort(all(a), cmp);
- retract(a, k);
- deque<int> rs;
- for (int i = 0; i < (int)a.size(); i++) {
- rs.push_back(a[i]);
- if (i + 1 < (int)a.size() && (a[i] + a[i + 1]) % k == 0) {
- if (!ost2.empty()) {
- rs.push_back(ost2.back());
- ost2.pop_back();
- }
- else if (!ost1.empty()) {
- rs.push_back(ost1.back());
- ost1.pop_back();
- }
- }
- }
- if ((int)ost1.size() < (int)ost2.size()) {
- ost1.swap(ost2);
- }
- deque<int> nw_rs;
- for (int i = 0; i < (int)rs.size(); i++) {
- nw_rs.push_back(rs[i]);
- if (i + 1 < (int)rs.size() && !ost1.empty() && (int)ost1.size() != (int)ost2.size() &&
- (rs[i] + ost1.back()) % k != 0 && (ost1.back() + rs[i + 1]) % k != 0) {
- nw_rs.push_back(ost1.back());
- ost1.pop_back();
- }
- }
- rs.swap(nw_rs);
- if (abs((int)ost1.size() - (int)ost2.size()) > 2) {
- cout << "NO\n";
- return 0;
- }
- if ((int)ost1.size() < (int)ost2.size()) {
- ost1.swap(ost2);
- }
- while (!ost1.empty() && !ost2.empty()) {
- rs.push_front(ost1.back());
- rs.push_front(ost2.back());
- ost1.pop_back();
- ost2.pop_back();
- }
- if (!ost1.empty()) {
- rs.push_back(ost1.back());
- ost1.pop_back();
- }
- if (!ost1.empty()) {
- rs.push_front(ost1.back());
- ost1.pop_back();
- }
- bool ok = true;
- if (!ost1.empty() || !ost2.empty()) {
- ok = false;
- }
- for (int i = 0; i + 1 < n; i++) {
- if ((rs[i] + rs[i + 1]) % k == 0) {
- ok = false;
- break;
- }
- }
- if (ok) {
- cout << "YES\n";
- for (int& i : rs) {
- cout << i << ' ';
- }
- }
- else {
- cout << "NO\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement