Submission #15340

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
15340	2015-07-12T06:21:28 Z	myungwoo	통로 위의 개미 (kriii3_X)	C++14	0 / 85	747 ms	7868 KB

X

#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;
vector <int> C;

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

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)
{
	int ret = -1;
	for (int i=0;i<n;i++) if (get_grundy(i) == g) ret = i;
	/*
	lld s = 0, 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)
{
	int ret = 0;
	for (int i=1;i<n;i++) if (invalid(i) > invalid(i-1)) ret = i;
	/*
	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);
	}
	int V = 0;
	for (int i=1;i<=K;i++){
		scanf("%lld", A+i);
		V = max(V, (int)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]++;
	}
	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 = 0, q = 0;
		for (int j=0;j<A[i];j++) if (get_grundy(j) == ox) p++, q = A[i] - j;
		/*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 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	747 ms	7868 KB	Program hung waiting for input
2	Halted	0 ms	0 KB	-

Subtask #2

0.0 / 55.0

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