Submission #15435

#	Time	Username	Problem	Language	Result	Execution time	Memory
15435		myungwoo	로봇 심판의 님 게임 (kriii3_F)	C++14	28 / 79	2000 ms	3136 KiB

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 / 28
• Subtask 2: 0 / 51