fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n, d, k, pre2[101], pre3[101][101];
  5. vector<int> v[100001];
  6.  
  7. vector<int> operator+(vector<int> a, vector<int> b) {
  8. 	vector<int> r(d);
  9. 	for (int i = 0; i < d; i ++) r[i] = a[i] + b[i] % k;
  10. 	return r;
  11. }
  12.  
  13. int operator*(vector<int> a, vector<int> b) {
  14. 	int s = 0;
  15. 	for (int i = 0; i < d; i ++) s = (s + a[i] * b[i]) % k;
  16. 	return s;
  17. }
  18.  
  19. void check(int i) {
  20. 	for (int j = 0; j < i; j ++) {
  21. 		if (v[i] * v[j] == 0) {
  22. 			int x = v[i][d];
  23. 			int y = v[j][d];
  24. 			if (x > y) swap(x, y);
  25. 			cout << x << " " << y << '\n';
  26. 			return;
  27. 		}
  28. 	}
  29. }
  30.  
  31. signed main() {
  32. 	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  33.  
  34. 	cin >> n >> d >> k;
  35. 	for (int i = 0; i < n; i ++) {
  36. 		v[i] = vector<int>(d + 1);
  37. 		for (int j = 0; j < d; j ++) {
  38. 			cin >> v[i][j];
  39. 			v[i][j] %= k;
  40. 		}
  41. 		v[i][d] = i + 1; // index for random shuffle
  42. 	}
  43. 	random_shuffle(v, v + n);
  44. 	if (k == 2) {
  45. 		for (int i = 0; i < n; i ++) {
  46. 			vector<int> x = v[i];
  47. 			int s = 0;
  48. 			for (int j = 0; j < d; j ++) {
  49. 				s = (s + x[j] * pre2[j]) % k;
  50. 				pre2[j] = (pre2[j] + x[j]) % k;
  51. 			}
  52. 			if (s % 2 != i % 2) {
  53. 				check(i);
  54. 				return 0;
  55. 			}
  56. 		}
  57. 		cout << "-1 -1\n";
  58. 	} else {
  59. 		for (int i = 0; i < n; i ++) {
  60. 			vector<int> x = v[i];
  61. 			int s = 0;
  62. 			for (int j = 0; j < d; j ++) {
  63. 				for (int l = 0; l < d; l ++) {
  64. 					s = (s + x[j] * x[l] * pre3[j][l]) % k;
  65. 					pre3[j][l] += x[j] * x[l];
  66. 				}
  67. 			}
  68. 			if (s % 3 != i % 3) {
  69. 				check(i);
  70. 				return 0;
  71. 			}
  72. 		}
  73. 		cout << "-1 -1\n";
  74. 	}
  75. }
  76.  
  77. /*
  78. input:
  79. 3 5 2 
  80. 1 0 1 0 1 
  81. 1 1 0 1 0 
  82. 0 1 0 1 1
  83.  
  84. output:
  85. 2 3
  86. */
  87.  
Success #stdin #stdout 0s 6080KB
comments (?)
stdin
copy 
3 5 2 
1 0 1 0 1 
1 1 0 1 0 
0 1 0 1 1
stdout
copy 
2 3
https://ideone.com/Z8yqiY
language:
C++14 (gcc 8.3)
created:
3 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!