Advertisement
erek1e

POI Task Game

Jul 18th, 2022
826
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.83 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. int main() {
  7.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  8.     int m, n; cin >> m >> n;
  9.     vector<pair<int, int>> groups;
  10.     for (int i = 0; i < n; ++i) {
  11.         int x; cin >> x;
  12.         if (!groups.empty() && groups.back().second + 1 == x) ++groups.back().second;
  13.         else groups.emplace_back(x, x);
  14.     }
  15.  
  16.     if (groups.back().second == m-1) {
  17.         cout << groups.back().second - groups.back().first + 1 << endl;
  18.         return 0;
  19.     }
  20.  
  21.     int k = groups.size();
  22.     vector<bool> evenGroup(groups.size());
  23.     groups.emplace_back(m, m);
  24.     evenGroup.push_back(true);
  25.    
  26.     int XOR = 0;
  27.     for (int i = k-1; i >= 0; --i) {
  28.         evenGroup[i] = evenGroup[i+1] ^ ((groups[i+1].first - groups[i].second + 1) & 1);
  29.         if (evenGroup[i]) XOR = XOR ^ (groups[i].second-groups[i].first+1);
  30.     }
  31.     if (XOR == 0) {
  32.         cout << 0 << endl;
  33.         return 0;
  34.     }
  35.  
  36.     int winningMoves = 0;
  37.     for (int i = 0; i < k; ++i) {
  38.         if (evenGroup[i]) {
  39.             int curSize = (groups[i].second-groups[i].first+1);
  40.             int newSize = curSize ^ XOR; // to make XOR == 0
  41.             if (newSize < curSize) ++winningMoves;
  42.             else if (newSize > curSize) {
  43.                 // previous (odd) group needs to be non-empty and have at least new-cur
  44.                 if (groups[i-1].second+2 == groups[i].first &&
  45.                     groups[i-1].second-groups[i-1].first+1 >= newSize-curSize) ++winningMoves;
  46.             }
  47.         } else {
  48.             // add case where next group is even and empty
  49.             int curSize = (groups[i].second-groups[i].first+1);
  50.             if (curSize >= XOR && groups[i].second+2 < groups[i+1].first) ++winningMoves;
  51.         }
  52.     }
  53.     cout << winningMoves << endl;
  54.     return 0;
  55. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement