oj.uz

Submission #15504

# Submission time Handle Problem Language Result Execution time Memory
15504 2015-07-12T08:35:20 Z xhae 로봇 심판의 님 게임 (kriii3_F) C++14
0 / 79
 2000 ms 1720 KB 
#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 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 > num) break;
        }
      }
      res += flip2 * (num / lcm2);
    }
  }

  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 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
0.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 939 ms 1720 KB Output is correct
2 Correct 410 ms 1720 KB Output is correct
3 Correct 331 ms 1720 KB Output is correct
4 Correct 476 ms 1720 KB Output is correct
5 Correct 577 ms 1720 KB Output is correct
6 Correct 350 ms 1720 KB Output is correct
7 Execution timed out 2000 ms 1720 KB Program timed out
8 Halted 0 ms 0 KB -

Subtask #2
0.0 / 51.0

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