Submission #15435

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
15435	2015-07-12T07:39:33 Z	myungwoo	로봇 심판의 님 게임 (kriii3_F)	C++14	28 / 79	2000 ms	3136 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];
lld lcmP[1<<16], lcmQ[1<<16]; int bitcnt[1<<16];
bool overP[1<<16], overQ[1<<16];
vector <lld> P, Q;
map <lld, lld> container;
 
lld gcd(lld a, lld b){ return b ? gcd(b, a%b) : a; }

inline lld invalid(lld n)
{
	bool exists = container.count(n);
	lld &ret = container[n];
	if (exists) return ret;
	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++){
			if (overQ[msk2]) continue;
			lld g = gcd(lcmP[msk1], lcmQ[msk2]);
			lld lcm = lcmP[msk1];
			if (lcm / g > n / lcmQ[msk2]) continue;
			lcm = lcm / g * lcmQ[msk2];
			if (msk1 + msk2) ret -= ((bitcnt[msk1] + bitcnt[msk2]) & 1 ? 1 : -1) * n / lcm;
		}
	}
	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;
		}
	}
	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);
	}
}

Subtask #1

28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	58 ms	3136 KB	Output is correct
2	Correct	50 ms	3136 KB	Output is correct
3	Correct	76 ms	3136 KB	Output is correct
4	Correct	127 ms	3136 KB	Output is correct
5	Correct	170 ms	3136 KB	Output is correct
6	Correct	55 ms	3136 KB	Output is correct
7	Correct	41 ms	3136 KB	Output is correct
8	Correct	54 ms	3136 KB	Output is correct
9	Correct	50 ms	3136 KB	Output is correct
10	Correct	53 ms	3136 KB	Output is correct
11	Correct	17 ms	3136 KB	Output is correct
12	Correct	23 ms	3136 KB	Output is correct
13	Correct	23 ms	3136 KB	Output is correct
14	Correct	14 ms	3136 KB	Output is correct
15	Correct	20 ms	3136 KB	Output is correct
16	Correct	23 ms	3136 KB	Output is correct
17	Correct	19 ms	3136 KB	Output is correct
18	Correct	23 ms	3136 KB	Output is correct
19	Correct	11 ms	3136 KB	Output is correct
20	Correct	12 ms	3136 KB	Output is correct
21	Correct	12 ms	3136 KB	Output is correct
22	Correct	10 ms	3136 KB	Output is correct
23	Correct	9 ms	3136 KB	Output is correct
24	Correct	34 ms	3136 KB	Output is correct
25	Correct	21 ms	3136 KB	Output is correct
26	Correct	14 ms	3136 KB	Output is correct
27	Correct	28 ms	3136 KB	Output is correct
28	Correct	8 ms	3136 KB	Output is correct
29	Correct	10 ms	3136 KB	Output is correct
30	Correct	7 ms	3136 KB	Output is correct
31	Correct	0 ms	3136 KB	Output is correct
32	Correct	0 ms	3136 KB	Output is correct
33	Correct	0 ms	3136 KB	Output is correct
34	Correct	0 ms	3136 KB	Output is correct
35	Correct	0 ms	3136 KB	Output is correct

Subtask #2

0.0 / 51.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	3136 KB	Output is correct
2	Correct	0 ms	3136 KB	Output is correct
3	Correct	337 ms	3136 KB	Output is correct
4	Execution timed out	2000 ms	3136 KB	Program timed out
5	Halted	0 ms	0 KB	-