Submission #15489

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
15489	2015-07-12T08:25:59 Z	xhae	로봇 심판의 님 게임 (kriii3_F)	C++14	0 / 79	6 ms	1720 KB

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<int> P, Q, cnt;

long long calc(long long num) {
  long long res = 0;
  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 > num) break;
      }
    if (lcm > num) continue;
    for (int i=0; i<M; i++) {
      lcm = lcm * Q[i] / __gcd(lcm, 0LL + Q[i]);
      if (lcm > num) break;
    }
    res += flip * (num / lcm);
  }

  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];

  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 target = calc(cnt[i]) ^ xx;
      if (target < calc(cnt[i])) {
        if (target == 0) {
          ra = cnt[i] + 1 - calc(cnt[i]);
          long long ll = 0;
          long long rr = cnt[i] - 1;
          while (ll < rr) {
            long long mid = (ll + rr) / 2;
            if (calc(cnt[i]) - 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

0.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	6 ms	1720 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2

0.0 / 51.0

#	Verdict	Execution time	Memory	Grader output
1	Halted	0 ms	0 KB	-