This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long lld;
int N, M, K;
lld A[21], G[21];
vector <lld> P, Q;
vector <int> C;
inline lld invalid(lld n)
{
return C[n];
}
inline lld get_grundy(lld n)
{
if (!n) return 0;
lld me = invalid(n), you = invalid(n-1);
return me > you ? 0 : (n - me);
}
inline lld get_number_with_grundy(lld g, lld n)
{
int ret = -1;
for (int i=0;i<n;i++) if (get_grundy(i) == g) ret = i;
/*
lld s = 0, e = n - 1, ret = 0;
while (s <= e){
lld m = (s+e) >> 1;
if (m - invalid(m) >= g) e = m-1, ret = m;
else s = m+1;
}*/
return ret;
}
inline lld get_number_robot_delete(lld n)
{
int ret = 0;
for (int i=1;i<n;i++) if (invalid(i) > invalid(i-1)) ret = i;
/*
lld s = 0, e = n - 2, ret = n - 1;
lld v = invalid(n - 1);
while (s <= e){
lld m = (s+e) >> 1;
if (invalid(m) >= v) e = m-1, ret = m;
else s = m+1;
}*/
return ret;
}
int main()
{
scanf("%d%d%d", &N, &M, &K);
for (int i=0;i<N;i++){
lld x; scanf("%lld", &x); P.pb(x);
}
for (int i=0;i<M;i++){
lld x; scanf("%lld", &x); Q.pb(x);
}
int V = 0;
for (int i=1;i<=K;i++){
scanf("%lld", A+i);
V = max(V, (int)A[i]);
}
C.resize(V+1, 0);
for (int i=1;i<=V;i++){
C[i] = C[i-1];
bool sw = 0;
for (int j=0;j<N;j++){
if (i % P[j] == 0) sw = 1;
}
for (int j=0;j<M;j++){
if (i % Q[j] != 0) sw = 1;
}
if (sw) C[i]++;
}
lld x = 0;
for (int i=1;i<=K;i++){
G[i] = get_grundy(A[i]);
x ^= G[i];
}
for (int i=1;i<=K;i++){
if (!G[i]){ puts("0 0"); continue; }
lld ox = x ^ G[i];
lld p = 0, q = 0;
for (int j=0;j<A[i];j++) if (get_grundy(j) == ox) p++, q = A[i] - j;
/*if (ox){
if (ox < G[i]) p = 1, q = A[i] - get_number_with_grundy(ox, A[i]);
else p = q = 0;
}else{
p = A[i] - G[i] + 1;
q = A[i] - get_number_robot_delete(A[i]);
}*/
printf("%lld %lld\n", p, q);
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |