Submission #15374

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
15374	2015-07-12T06:53:57 Z	myungwoo	로봇 심판의 님 게임 (kriii3_F)	C++14	28 / 79	263 ms	524288 KB

S

#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);
}
 
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;
        }
        bool sw2 = 1;
        for (int j=0;j<M;j++){
            if (i % Q[j] == 0) sw2 = 0;
        }
        if (sw || sw2) 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;
        printf("%lld %lld\n", p, q);
    }
}

Subtask #1

28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	263 ms	5616 KB	Output is correct
2	Correct	234 ms	5520 KB	Output is correct
3	Correct	222 ms	5228 KB	Output is correct
4	Correct	218 ms	5132 KB	Output is correct
5	Correct	246 ms	5508 KB	Output is correct
6	Correct	247 ms	5612 KB	Output is correct
7	Correct	248 ms	5628 KB	Output is correct
8	Correct	241 ms	5628 KB	Output is correct
9	Correct	220 ms	5212 KB	Output is correct
10	Correct	243 ms	5592 KB	Output is correct
11	Correct	216 ms	5428 KB	Output is correct
12	Correct	253 ms	5628 KB	Output is correct
13	Correct	237 ms	5584 KB	Output is correct
14	Correct	232 ms	5396 KB	Output is correct
15	Correct	212 ms	4984 KB	Output is correct
16	Correct	247 ms	5524 KB	Output is correct
17	Correct	222 ms	5188 KB	Output is correct
18	Correct	240 ms	5396 KB	Output is correct
19	Correct	251 ms	5572 KB	Output is correct
20	Correct	246 ms	5620 KB	Output is correct
21	Correct	255 ms	5628 KB	Output is correct
22	Correct	213 ms	5088 KB	Output is correct
23	Correct	244 ms	5556 KB	Output is correct
24	Correct	248 ms	5588 KB	Output is correct
25	Correct	244 ms	5556 KB	Output is correct
26	Correct	226 ms	5624 KB	Output is correct
27	Correct	252 ms	5612 KB	Output is correct
28	Correct	249 ms	5628 KB	Output is correct
29	Correct	237 ms	5464 KB	Output is correct
30	Correct	233 ms	5512 KB	Output is correct
31	Correct	81 ms	5628 KB	Output is correct
32	Correct	73 ms	5252 KB	Output is correct
33	Correct	75 ms	5312 KB	Output is correct
34	Correct	80 ms	5628 KB	Output is correct
35	Correct	71 ms	5528 KB	Output is correct

Subtask #2

0.0 / 51.0

#	Verdict	Execution time	Memory	Grader output
1	Memory limit exceeded	2 ms	524288 KB	Memory limit exceeded
2	Halted	0 ms	0 KB	-