cosenza987

Untitled

Aug 10th, 2025
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.34 KB | None | 0 0
  1. //Слава Україні, Героям слава
  2.  
  3. #pragma GCC optimize("O3")
  4.  
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. int main() {
  10.     ios_base::sync_with_stdio(false);
  11.     cin.tie(nullptr);
  12.     int n;
  13.     cin >> n;
  14.     vector<pair<int, int>> v(n);
  15.     for(auto &[a, b] : v) cin >> a >> b;
  16.     if(n >= 30) {
  17.         n = 30;
  18.         v.resize(30);
  19.     }
  20.     map<pair<int, int>, pair<int, int>> mp;
  21.     pair<int, int> cur;
  22.     auto p3 = [&](int x) -> int {
  23.         int ans = 1;
  24.         for(int j = 0; j < x; j++) ans *= 3;
  25.         return ans;
  26.     };
  27.     int fp3 = p3(n / 2);
  28.     for(int msk = 0; msk < fp3; msk++) {
  29.         int tmp = msk, mskl = 0, mskr = 0;
  30.         pair<int, int> cur;
  31.         for(int i = 0; i < n / 2; i++) {
  32.             if(tmp % 3 == 1) {
  33.                 cur.first += v[i].first;
  34.                 cur.second += v[i].second;
  35.                 mskl ^= (1 << i);
  36.             } else if(tmp % 3 == 2) {
  37.                 cur.first -= v[i].first;
  38.                 cur.second -= v[i].second;
  39.                 mskr ^= (1 << i);
  40.             }
  41.             tmp /= 3;
  42.         }
  43.         mp[cur] = {mskl, mskr};
  44.     }
  45.     fp3 = p3((n + 1) / 2);
  46.     int ansl = 0, ansr = 0;
  47.     bool foi = false;
  48.     for(int msk = 0; msk < fp3; msk++) {
  49.         int tmp = msk, mskl = 0, mskr = 0;
  50.         pair<int, int> cur;
  51.         for(int i = n / 2; i < n; i++) {
  52.             if(tmp % 3 == 1) {
  53.                 cur.first -= v[i].first;
  54.                 cur.second -= v[i].second;
  55.                 mskl ^= (1 << i);
  56.             } else if(tmp % 3 == 2) {
  57.                 cur.first += v[i].first;
  58.                 cur.second += v[i].second;
  59.                 mskr ^= (1 << i);
  60.             }
  61.             tmp /= 3;
  62.         }
  63.         if(mp.find(cur) != mp.end()) {
  64.             ansl = mskl ^ mp[cur].first;
  65.             ansr = mskr ^ mp[cur].second;
  66.             if (!ansl or !ansr) continue;
  67.             foi = true;
  68.             break;
  69.         }
  70.     }
  71.     if(!foi) {
  72.         cout << "yes\n";
  73.         return 0;
  74.     }
  75.     cout << "no\n";
  76.     cout << __builtin_popcount(ansl) << " ";
  77.     for(int i = 0; i < 30; i++) if((ansl >> i) & 1) cout << (i + 1) << " ";
  78.     cout << "\n";
  79.     cout << __builtin_popcount(ansr) << " ";
  80.     for (int i = 0; i < 30; i++) if ((ansr >> i) & 1) cout << (i + 1) << " ";
  81.     cout << "\n";
  82.     return 0;
  83. }
Advertisement
Add Comment
Please, Sign In to add comment