1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
| #include <algorithm>
#include <iostream>
#include <cstring>
#include <cassert>
#include <cstdlib>
#include <cstdio>
#include <ctime>
using namespace std;
int n, d, k, a[100005][105], b[105][100005], tot, c[100005], e[100005], f[100005], g[105][105];
int calc(int x){
int tot=0;
for(int i=1; i<=d; i++)
for(int j=1; j<=d; j++){
tot += g[i][j] * a[x][i] * a[x][j];
g[i][j] += a[x][i] * a[x][j];
}
return tot%3;
}
int main(){
srand(time(NULL));
cin>>n>>d>>k;
for(int i=1; i<=n; i++)
for(int j=1; j<=d; j++){
scanf("%d", &a[i][j]);
a[i][j] %= k;
b[j][i] = a[i][j];
}
if(k==2){
int T=6;
while(T--){
tot = 0;
for(int i=1; i<=n; i++){
c[i] = rand() % 2;
tot += c[i];
}
tot %= 2;
memset(e, 0, sizeof(e));
memset(f, 0, sizeof(f));
for(int i=1; i<=d; i++){
for(int j=1; j<=n; j++)
e[i] += b[i][j] * c[j];
e[i] %= 2;
}
for(int i=1; i<=n; i++){
for(int j=1; j<=d; j++)
f[i] += a[i][j] * e[j];
f[i] %= 2;
}
int tag1=-1;
for(int i=1; i<=n; i++)
if(f[i]!=tot){
tag1 = i;
break;
}
if(tag1==-1) continue;
int tag2=-1;
for(int i=1; i<=n; i++){
if(i==tag1) continue;
int now=0;
for(int j=1; j<=d; j++)
now += a[tag1][j] * a[i][j];
now %= 2;
if(!now){
tag2 = i;
break;
}
}
if(tag2!=-1){
if(tag1>tag2) swap(tag1, tag2);
printf("%d %d\n", tag1, tag2);
return 0;
}
}
printf("-1 -1\n");
}
else{
for(int i=1; i<=n; i++) c[i] = i;
random_shuffle(c+1, c+1+n);
for(int i=1; i<=n; i++){
if(calc(c[i])!=(i-1)%3){
for(int j=1; j<i; j++){
int tot=0;
for(int l=1; l<=d; l++)
tot += a[c[i]][l] * a[c[j]][l];
tot %= 3;
if(!tot){
if(c[i]>c[j]) swap(c[i], c[j]);
printf("%d %d\n", c[i], c[j]);
return 0;
}
}
}
}
printf("-1 -1\n");
}
return 0;
}
|