Advertisement
ivnikkk

Untitled

Jan 20th, 2023
740
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.30 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include "bits/stdc++.h"
  3. using namespace std;
  4. #define all(a) a.begin(), a.end()
  5. #define int long long
  6. void retract(vector<int>& a, int k) {
  7.     int n = (int)a.size();
  8.     map<int, vector<int>> cnt;
  9.     for (int i = 0; i < n; i++) {
  10.         cnt[a[i] % k].push_back(a[i]);
  11.     }
  12.     vector<int> b;
  13.     for (auto& it : cnt) {
  14.         b.push_back(it.first);
  15.     }
  16.     for (int i = 0; i < (int)b.size(); i++) {
  17.         if (i + 1 < (int)b.size()) {
  18.             if ((b[i] + b[i + 1]) % k == 0) {
  19.                 swap(b[i], b[i - 1 >= 0 ? i - 1 : (int)b.size() - 1]);
  20.             }
  21.         }
  22.     }
  23.     a.clear();
  24.     for (int i = 0; i < (int)b.size(); i++) {
  25.         for (int& j : cnt[b[i]]) {
  26.             a.push_back(j);
  27.         }
  28.     }
  29. }
  30. signed main() {
  31. #ifdef _DEBUG
  32.     freopen("input.txt", "r", stdin);
  33.     freopen("output.txt", "w", stdout);
  34. #endif
  35.     ios_base::sync_with_stdio(false);
  36.     cin.tie(nullptr);
  37.     int n, k; cin >> n >> k;
  38.     vector<int> a;
  39.     vector<int> ost1, ost2;
  40.     for (int i = 0; i < n; i++) {
  41.         int x; cin >> x;
  42.         int o = x % k;
  43.         if (o == 0) {
  44.             ost1.push_back(x);
  45.         }
  46.         else if (k % 2 == 0 && o == k / 2) {
  47.             ost2.push_back(x);
  48.         }
  49.         else {
  50.             a.push_back(x);
  51.         }
  52.     }
  53.     auto cmp = [&](const int& lhs, const int& rhs) {
  54.         return lhs % k < rhs % k;
  55.     };
  56.     sort(all(a), cmp);
  57.     retract(a, k);
  58.     deque<int> rs;
  59.     for (int i = 0; i < (int)a.size(); i++) {
  60.         rs.push_back(a[i]);
  61.         if (i + 1 < (int)a.size() && (a[i] + a[i + 1]) % k == 0) {
  62.             if (!ost2.empty()) {
  63.                 rs.push_back(ost2.back());
  64.                 ost2.pop_back();
  65.             }
  66.             else if (!ost1.empty()) {
  67.                 rs.push_back(ost1.back());
  68.                 ost1.pop_back();
  69.             }
  70.         }
  71.     }
  72.     if ((int)ost1.size() < (int)ost2.size()) {
  73.         ost1.swap(ost2);
  74.     }
  75.     deque<int> nw_rs;
  76.     for (int i = 0; i < (int)rs.size(); i++) {
  77.         nw_rs.push_back(rs[i]);
  78.         if (i + 1 < (int)rs.size() && !ost1.empty() && (int)ost1.size() != (int)ost2.size() &&
  79.             (rs[i] + ost1.back()) % k != 0 && (ost1.back() + rs[i + 1]) % k != 0) {
  80.             nw_rs.push_back(ost1.back());
  81.             ost1.pop_back();
  82.         }
  83.     }
  84.     rs.swap(nw_rs);
  85.     if (abs((int)ost1.size() - (int)ost2.size()) > 2) {
  86.         cout << "NO\n";
  87.         return 0;
  88.     }
  89.     if ((int)ost1.size() < (int)ost2.size()) {
  90.         ost1.swap(ost2);
  91.     }
  92.     while (!ost1.empty() && !ost2.empty()) {
  93.         rs.push_front(ost1.back());
  94.         rs.push_front(ost2.back());
  95.         ost1.pop_back();
  96.         ost2.pop_back();
  97.     }
  98.     if (!ost1.empty()) {
  99.         rs.push_back(ost1.back());
  100.         ost1.pop_back();
  101.     }
  102.     if (!ost1.empty()) {
  103.         rs.push_front(ost1.back());
  104.         ost1.pop_back();
  105.     }
  106.     bool ok = true;
  107.     if (!ost1.empty() || !ost2.empty()) {
  108.         ok = false;
  109.     }
  110.     for (int i = 0; i + 1 < n; i++) {
  111.         if ((rs[i] + rs[i + 1]) % k == 0) {
  112.             ok = false;
  113.             break;
  114.         }
  115.     }
  116.     if (ok) {
  117.         cout << "YES\n";
  118.         for (int& i : rs) {
  119.             cout << i << ' ';
  120.         }
  121.     }
  122.     else {
  123.         cout << "NO\n";
  124.     }
  125. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement