Codeforces Round 850 (Div. 2, based on VK Cup 2022 - Final Round) - A2. AAlternating Deck (hard version) (800)

A2. AAlternating Deck (hard version)

잘 구현해서 구간에 존재하는 홀수의 개수와 짝수의 개수를 정답에 더해주면 된다.

void solve() {
   int n;
   cin >> n;
   vvi ans(2, vi(2));
   n--;
 
   // 홀수 = 하얀색
   // 짝수 = 검은색
 
   ans[0][0] = 1;
   int nxt = 2, parity = 1;
   int nxt_i = 2;
   while (n) {
      int cur = min(n, 2 * nxt + 1);
 
      int l = nxt_i, r = l + cur - 1;
      int even = r / 2 - (l - 1) / 2;
      int odd = r - l + 1 - even;
 
      ans[parity][0] += odd;
      ans[parity][1] += even;
      n -= even + odd;
 
      nxt += 2;
      parity ^= 1;
      nxt_i = r + 1;
   }
   cout << ans[0][0] << ' ' << ans[0][1] << ' ' << ans[1][0] << ' ' << ans[1][1] << endl;
}