#include using namespace std; int n, m, b; int S[1023][1023]; //random_device randDev; //mt19937 randGen(randDev()); clock_t startTime; inline bool haveTime() { return (clock() - startTime) < 4.6 * CLOCKS_PER_SEC; } int permToN[1024]; void chooseK(int k) { for (int i = 0; i < k-1; ++i) { int swapIdx = i + (rand() % (n-i)); //uniform_int_distribution<>(i, n-1)(randGen); if (swapIdx != i) swap(permToN[i], permToN[swapIdx]); } } inline int calcScore(int k) { int res = 0; for (int i = 0; i < m; ++i) { int resi = 0; for (int ji = 0; ji < k; ++ji) { resi += S[i][permToN[ji]]; } resi %= b; res += resi*resi; } return res; } int main() { startTime = clock(); freopen("subsetselection.in", "r", stdin); freopen("subsetselection.out", "w", stdout); scanf("%d %d %d", &n, &m, &b); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { scanf("%d", &S[j][i]); } } for (int i = 0; i < n; ++i) permToN[i]=i; int bestRes = 0; int best[1024]; int bestk = 0; int ITERATIONS = 0; //uniform_int_distribution<> randDistribution(1,n); #ifndef ONLINE_JUDGE clock_t timeInCalcScore = 0; clock_t timeInChooseK = 0; clock_t aa,bb; #endif while (haveTime()) { ITERATIONS++; int k = 1 + (rand() % n); //randDistribution(randGen); #ifndef ONLINE_JUDGE bb=clock(); #endif chooseK(k); #ifndef ONLINE_JUDGE aa=clock(); timeInChooseK += aa-bb; #endif #ifndef ONLINE_JUDGE bb = clock(); #endif int score = calcScore(k); #ifndef ONLINE_JUDGE aa = clock(); timeInCalcScore += aa-bb; #endif if (score > bestRes) { #ifndef ONLINE_JUDGE fprintf(stderr, "IMPROVEMENT: OLD: %d, NEW: %d\n", bestRes, score); #endif bestRes = score; bestk = k; //for (int i = 0; i < k; ++i) best[i] = permToN[i]; memcpy(best, permToN, k * sizeof(int)); } } #ifndef ONLINE_JUDGE fprintf(stderr, "Optimization iterations: %d\n", ITERATIONS); fprintf(stderr, "Time in calcScore: %.5lf seconds\n", 1.0*timeInCalcScore / CLOCKS_PER_SEC); fprintf(stderr, "Time in chooseK: %.5lf seconds\n", 1.0*timeInChooseK / CLOCKS_PER_SEC); #endif printf("%d\n", bestk); for (int i = 0; i < bestk; ++i) { printf("%d\n", best[i]+1); } return 0; }