fork download
  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
stdin
3 5 2 
1 0 1 0 1 
1 1 0 1 0 
0 1 0 1 1
stdout
2 3