Submission #15419

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
15419	2015-07-12T07:24:47 Z	myungwoo	로봇 심판의 님 게임 (kriii3_F)	C++14	0 / 79	2000 ms	1724 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;
 
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++){
		int sign = -1;
		lld lcm = 1;
		bool none = 0;
		for (int i=0;i<N;i++) if (msk1 & (1 << i)){
			sign *= -1;
			lld g = gcd(lcm, P[i]);
			if (P[i] / g > n / lcm){ none = 1; break; }
			lcm = P[i] / g * lcm;
		}
		if (none) continue;
		if (msk1) ret += sign * n / lcm;
		// if (msk1) printf("|A| += %lld\n", sign * n / lcm);
		for (int msk2=0;msk2<(1<<M);msk2++){
			int sign2 = sign; lld lcm2 = lcm;
			bool over = 0;
			for (int i=0;i<M;i++) if (msk2 & (1 << i)){
				sign2 *= -1;
				lld g = gcd(lcm2, Q[i]);
				if (Q[i] / g > n / lcm2){ over = 1; break; }
				lcm2 = Q[i] / g * lcm2;
			}
			if (over) continue;
			if (msk1 + msk2) ret -= (lld)sign2 * n / lcm2;
			// if (msk1 + msk2) printf("|A or B| += %lld (%d %d)\n", sign2 * n / lcm2, msk1, msk2);
		}
	}
	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);
	}
	for (int i=1;i<=K;i++) scanf("%lld", A+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<10;i++) printf("%d: %lld\n", i, get_grundy(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

0.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	928 ms	1724 KB	Output is correct
2	Correct	386 ms	1724 KB	Output is correct
3	Correct	289 ms	1724 KB	Output is correct
4	Correct	422 ms	1724 KB	Output is correct
5	Correct	523 ms	1724 KB	Output is correct
6	Correct	337 ms	1724 KB	Output is correct
7	Execution timed out	2000 ms	1724 KB	Program timed out
8	Halted	0 ms	0 KB	-

Subtask #2

0.0 / 51.0

#	Verdict	Execution time	Memory	Grader output
1	Halted	0 ms	0 KB	-