Submission #15433

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
15433	2015-07-12T07:37:59 Z	myungwoo	로봇 심판의 님 게임 (kriii3_F)	C++14	28 / 79	2000 ms	3132 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;
 
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++){
			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	167 ms	3132 KB	Output is correct
2	Correct	111 ms	3132 KB	Output is correct
3	Correct	83 ms	3132 KB	Output is correct
4	Correct	140 ms	3132 KB	Output is correct
5	Correct	186 ms	3132 KB	Output is correct
6	Correct	60 ms	3132 KB	Output is correct
7	Correct	42 ms	3132 KB	Output is correct
8	Correct	55 ms	3132 KB	Output is correct
9	Correct	54 ms	3132 KB	Output is correct
10	Correct	60 ms	3132 KB	Output is correct
11	Correct	17 ms	3132 KB	Output is correct
12	Correct	23 ms	3132 KB	Output is correct
13	Correct	23 ms	3132 KB	Output is correct
14	Correct	21 ms	3132 KB	Output is correct
15	Correct	21 ms	3132 KB	Output is correct
16	Correct	24 ms	3132 KB	Output is correct
17	Correct	19 ms	3132 KB	Output is correct
18	Correct	25 ms	3132 KB	Output is correct
19	Correct	11 ms	3132 KB	Output is correct
20	Correct	13 ms	3132 KB	Output is correct
21	Correct	9 ms	3132 KB	Output is correct
22	Correct	11 ms	3132 KB	Output is correct
23	Correct	9 ms	3132 KB	Output is correct
24	Correct	37 ms	3132 KB	Output is correct
25	Correct	21 ms	3132 KB	Output is correct
26	Correct	17 ms	3132 KB	Output is correct
27	Correct	29 ms	3132 KB	Output is correct
28	Correct	8 ms	3132 KB	Output is correct
29	Correct	10 ms	3132 KB	Output is correct
30	Correct	8 ms	3132 KB	Output is correct
31	Correct	0 ms	3132 KB	Output is correct
32	Correct	0 ms	3132 KB	Output is correct
33	Correct	0 ms	3132 KB	Output is correct
34	Correct	0 ms	3132 KB	Output is correct
35	Correct	0 ms	3132 KB	Output is correct

Subtask #2

0.0 / 51.0

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