| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 15442 |
2015-07-12T07:43:19 Z |
myungwoo |
로봇 심판의 님 게임 (kriii3_F) |
C++14 |
|
171 ms |
3708 KB |
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long lld;
int N, M, K;
lld A[21], G[21];
lld lcmP[1<<16], lcmQ[1<<16], lcmPQ[1<<16]; int bitcnt[1<<16];
bool overP[1<<16], overQ[1<<16], overPQ[1<<16];
vector <lld> P, Q;
lld gcd(lld a, lld b){ return b ? gcd(b, a%b) : a; }
inline lld invalid(lld n)
{
lld ret = n;
for (int msk1=0;msk1<(1<<N);msk1++){
if (overP[msk1]) continue;
if (msk1) ret += (bitcnt[msk1] & 1 ? 1 : -1) * n / lcmP[msk1];
for (int msk2=0;msk2<(1<<M);msk2++){
int nmsk = (msk1 << M) | msk2;
if (overQ[msk2] || overPQ[nmsk]) continue;
if (msk1 + msk2) ret -= ((bitcnt[msk1] + bitcnt[msk2]) & 1 ? 1 : -1) * n / lcmPQ[nmsk];
}
}
return ret;
}
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)
{
lld s = 1, 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)
{
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);
}
lld V = 0;
for (int i=1;i<=K;i++) scanf("%lld", A+i), V = max(V, A[i]);
for (int msk=0;msk<(1<<(N+M));msk++){
for (int v=msk;v;v>>=1)
if (v & 1) bitcnt[msk]++;
}
for (int msk=0;msk<(1<<N);msk++){
lld &lcm = lcmP[msk];
bool &over = overP[msk];
lcm = 1;
for (int i=0;i<N;i++) if (msk & (1 << i)){
lld g = gcd(lcm, P[i]);
if (P[i] / g > V / lcm){ over = 1; break; }
lcm = P[i] / g * lcm;
}
}
for (int msk=0;msk<(1<<M);msk++){
lld &lcm = lcmQ[msk];
bool &over = overQ[msk];
lcm = 1;
for (int i=0;i<M;i++) if (msk & (1 << i)){
lld g = gcd(lcm, Q[i]);
if (Q[i] / g > V / lcm){ over = 1; break; }
lcm = Q[i] / g * lcm;
}
}
for (int msk1=0;msk1<(1<<N);msk1++){
for (int msk2=0;msk2<(1<<M);msk2++){
int nmsk = (msk1 << M) | msk2;
if (overP[msk1] || overQ[msk2]){ overPQ[nmsk] = 1; continue; }
lld g = gcd(lcmP[msk1], lcmQ[msk2]);
lld lcm = lcmP[msk1];
if (lcm / g > V / lcmQ[msk2]){ overPQ[nmsk] = 1; continue; }
lcmPQ[nmsk] = lcm / g * lcmQ[msk2];
}
}
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, q;
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 |
| 1 |
Correct |
18 ms |
3708 KB |
Output is correct |
| 2 |
Correct |
14 ms |
3708 KB |
Output is correct |
| 3 |
Correct |
11 ms |
3708 KB |
Output is correct |
| 4 |
Correct |
14 ms |
3708 KB |
Output is correct |
| 5 |
Correct |
17 ms |
3708 KB |
Output is correct |
| 6 |
Correct |
6 ms |
3708 KB |
Output is correct |
| 7 |
Correct |
20 ms |
3708 KB |
Output is correct |
| 8 |
Correct |
15 ms |
3708 KB |
Output is correct |
| 9 |
Correct |
12 ms |
3708 KB |
Output is correct |
| 10 |
Correct |
4 ms |
3708 KB |
Output is correct |
| 11 |
Correct |
14 ms |
3708 KB |
Output is correct |
| 12 |
Correct |
25 ms |
3708 KB |
Output is correct |
| 13 |
Correct |
24 ms |
3708 KB |
Output is correct |
| 14 |
Correct |
23 ms |
3708 KB |
Output is correct |
| 15 |
Correct |
22 ms |
3708 KB |
Output is correct |
| 16 |
Correct |
26 ms |
3708 KB |
Output is correct |
| 17 |
Correct |
17 ms |
3708 KB |
Output is correct |
| 18 |
Correct |
6 ms |
3708 KB |
Output is correct |
| 19 |
Correct |
4 ms |
3708 KB |
Output is correct |
| 20 |
Correct |
8 ms |
3708 KB |
Output is correct |
| 21 |
Correct |
7 ms |
3708 KB |
Output is correct |
| 22 |
Correct |
7 ms |
3708 KB |
Output is correct |
| 23 |
Correct |
7 ms |
3708 KB |
Output is correct |
| 24 |
Correct |
10 ms |
3708 KB |
Output is correct |
| 25 |
Correct |
21 ms |
3708 KB |
Output is correct |
| 26 |
Correct |
17 ms |
3708 KB |
Output is correct |
| 27 |
Correct |
27 ms |
3708 KB |
Output is correct |
| 28 |
Correct |
5 ms |
3708 KB |
Output is correct |
| 29 |
Correct |
6 ms |
3708 KB |
Output is correct |
| 30 |
Correct |
5 ms |
3708 KB |
Output is correct |
| 31 |
Correct |
0 ms |
3708 KB |
Output is correct |
| 32 |
Correct |
0 ms |
3708 KB |
Output is correct |
| 33 |
Correct |
0 ms |
3708 KB |
Output is correct |
| 34 |
Correct |
0 ms |
3708 KB |
Output is correct |
| 35 |
Correct |
0 ms |
3708 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
3708 KB |
Output is correct |
| 2 |
Correct |
0 ms |
3708 KB |
Output is correct |
| 3 |
Correct |
29 ms |
3708 KB |
Output is correct |
| 4 |
Correct |
171 ms |
3708 KB |
Output is correct |
| 5 |
Correct |
29 ms |
3708 KB |
Output is correct |
| 6 |
Correct |
15 ms |
3708 KB |
Output is correct |
| 7 |
Correct |
14 ms |
3708 KB |
Output is correct |
| 8 |
Correct |
45 ms |
3708 KB |
Output is correct |
| 9 |
Correct |
43 ms |
3708 KB |
Output is correct |
| 10 |
Correct |
39 ms |
3708 KB |
Output is correct |
