fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define rep(_i, _j) for(int _i = 1; _i <= _j; ++_i)
  3. const int INF = 0x3f3f3f3f;
  4. typedef long long LL;
  5. typedef double DB;
  6. using namespace std;
  7.  
  8.  
  9. int f, n;
  10. const int maxn = 100000 + 20;
  11. bool calced[maxn];
  12. int sg[maxn];
  13.  
  14. int work(int p) {
  15. 	if(calced[p]) {
  16. 		return sg[p];
  17. 	}
  18. 	calced[p] = true;
  19. 	if(p < f) {
  20. 		return sg[p] = 0;
  21. 	}
  22. 	bool hash[maxn];
  23. 	memset(hash, false, sizeof hash);
  24. 	for(int i = 2; i <= p; i = p / (p / i) + 1) {
  25. 		for(int j = i; j <= i + 1 && j <= p; ++j) {
  26. 			int status = 0;
  27. 			int time = p - (p / j) * j;
  28. 			if(time & 1) {
  29. 				status ^= work(p / j + 1);
  30. 			}
  31. 			if((j - time) & 1) {
  32. 				status ^= work(p / j);
  33. 			}
  34. 			hash[status] = true;
  35. 		}
  36. 	}
  37. 	for(int i = 0; ; ++i) {
  38. 		if(!hash[i]) {
  39. 			return sg[p] = i;
  40. 		}
  41. 	}
  42. }
  43.  
  44. int main() {
  45. 	int t, m;
  46. 	scanf("%d%d", &t, &f);
  47. 	while(t--) {
  48. 		scanf("%d", &n);
  49. 		int res = 0;
  50. 		for(int i = 1; i <= n; ++i) {
  51. 			scanf("%d", &m);
  52. 			res ^= work(m);
  53. 		}
  54. 		printf("%d", res > 0);
  55. 		if(t == 0) {
  56. 			puts("");
  57. 		} else {
  58. 			putchar(' ');
  59. 		}
  60. 	}
  61.  
  62. 	return 0;
  63. }
  64.  
Success #stdin #stdout 0s 3836KB
comments (?)
stdin
copy 
 4 3       

 1 1              

 1 2              

 1 3              

 1 5
stdout
copy 
0 0 1 1
https://ideone.com/wKrPtw
HNOI2014 江南乐
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!