Submission #15507

#	Time	Username	Problem	Language	Result	Execution time	Memory
15507		xhae	로봇 심판의 님 게임 (kriii3_F)	C++14	79 / 79	460 ms	2236 KiB

S

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;

int N, M, K;
vector<long long> P, Q, cnt;
vector<long long> lcms;

long long calc(long long num) {
  long long res = 0;
  for (int bit = 0; bit < (1 << N); bit ++) {
    for (int bit2 = 1; bit2 < (1 << M); bit2 ++) {
      long long val = lcms[bit * (1<<M) + bit2];
      if (val > 0) res += num / val;
      else if (val < 0) res -= num / (-val);
    }
  }

  return res;
}

int main()
{
  cin >> N >> M >> K;
  P.resize(N);
  Q.resize(M);
  cnt.resize(K);
  for (int i=0; i<N; i++) cin >> P[i];
  for (int i=0; i<M; i++) cin >> Q[i];
  for (int i=0; i<K; i++) cin >> cnt[i];

  lcms.resize(1<<(N+M));
  for (int bit = 0; bit < (1 << N); bit ++) {
    int flip = 1;
    long long lcm = 1;
    for (int i=0; i<N; i++)
      if (bit&(1<<i)) {
        lcm = lcm * P[i] / __gcd(lcm, 0LL + P[i]);
        flip = -flip;
        if (lcm > 1000000000000LL) break;
      }
    if (lcm > 1000000000000LL) continue;
    for (int bit2 = 1; bit2 < (1 << M); bit2 ++) {
      int flip2 = -flip;
      long long lcm2 = lcm;
      for (int i=0; i<M; i++) {
        if (bit2&(1<<i)) {
          lcm2 = lcm2 * Q[i] / __gcd(lcm2, 0LL + Q[i]);
          flip2 = -flip2;
          if (lcm2 > 1000000000000LL) break;
        }
      }
      lcms[bit * (1<<M) + bit2] = flip2 * lcm2;
    }
  }


  long long xx = 0;
  for (int i=0; i<K; i++)
    if (calc(cnt[i]) - calc(cnt[i] - 1) > 0)
      xx ^= calc(cnt[i]);

  for (int i=0; i<K; i++) {
    long long ra = 0, rb = 0;
    if (calc(cnt[i]) - calc(cnt[i] - 1) > 0) {
      long long my_cnt = calc(cnt[i]);
      long long target = my_cnt ^ xx;
      if (target < my_cnt) {
        if (target == 0) {
          ra = cnt[i] + 1 - my_cnt;
          long long ll = 0;
          long long rr = cnt[i] - 1;
          while (ll < rr) {
            long long mid = (ll + rr) / 2;
            if (my_cnt - calc(mid) != cnt[i] - mid) ll = mid + 1;
            else rr = mid;
          }
          rb = cnt[i] - ll;
        } else {
          ra = 1;
          long long ll = 0;
          long long rr = cnt[i] - 1;
          while (ll < rr) {
            long long mid = (ll + rr) / 2;
            if (calc(mid) < target) ll = mid + 1;
            else rr = mid;
          }
          rb = cnt[i] - ll;
        }
      }
    }
    cout << ra << " " << rb << endl;
  }
}

• Subtask 1: 28 / 28
• Subtask 2: 51 / 51