Submission #15276

#	Time	Username	Problem	Language	Result	Execution time	Memory
15276		myungwoo	로봇 심판의 님 게임 (kriii3_F)	C++14	0 / 79	105 ms	5616 KiB

S

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
typedef long long lld;

int N, M, K;
int A[21], G[21];
vector <int> P, Q;
vector <int> C;

inline lld invalid(lld n)
{
	return C[n];
}

inline lld get_grundy(lld n)
{
	return n - invalid(n);
}

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 - C[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 (C[m] >= v) e = m-1, ret = m;
		else s = m+1;
	}
	return ret;
}

int main()
{
	int V = 0;
	scanf("%d%d%d", &N, &M, &K);
	for (int i=0;i<N;i++){
		int x; scanf("%d", &x); P.pb(x);
	}
	for (int i=0;i<M;i++){
		int x; scanf("%d", &x); Q.pb(x);
	}
	for (int i=1;i<=K;i++){
		scanf("%d", A+i);
		V = max(V, 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;
		}
		for (int j=0;j<M;j++){
			if (i % Q[j] != 0) sw = 1;
		}
		if (sw) C[i]++;
	}
	int 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; }
		int 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];
			if (p) q = get_number_robot_delete(A[i]);
			else q = 0;
		}
		printf("%lld %lld\n", p, q);
	}
}

• Subtask 1: 0 / 28
• Subtask 2: 0 / 51