#pragma GCC optimize("Ofast") #include #define LL long long int #define ULL unsigned LL #define LD long double #define FI first #define SE second #define PB push_back #define PF push_front #define V vector #define PQ priority_queue #define ALL(x) x.begin(), x.end() #define SZ(x) (int)(x).size() #define FORI(i, a, b) for(int i = a; i < b ; ++i) #define FORD(i, a, b) for(int i = a; i > b ; --i) using namespace std; using pii = pair; const double TIME_LIMIT = 4.9; const double INF = 1e18; const clock_t START_T = clock(); double time_running(){ return (double)(clock() - START_T) / CLOCKS_PER_SEC; } void move(int steps, int& x, int& y, int& dx, int& dy, int& top, int& bottom, int& left, int& right){ int delta; while(steps){ if (dy){ if (dy == 1){ delta = min(steps, right - y); y += delta * dy; if (y == right){ dy = 0; dx = 1; top++; } } else { delta = min(steps, y - left); y += delta * dy; if (y == left){ dy = 0; dx = -1; bottom--; } } } else { if (dx == 1){ delta = min(steps, bottom - x); x += delta * dx; if (x == bottom){ dx = 0; dy = -1; right--; } } else { delta = min(steps, x - top); x += delta * dx; if (x == top){ dx = 0; dy = 1; left++; } } } steps -= delta; } } int main(){ ifstream cin("gerrymandering.in"); ofstream cout("gerrymandering.out"); mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int n, d, p; cin >> n >> d >> p; V> votes(n, V (n)); FORI(i,0,n){ FORI(j,0,n){ cin >> votes[i][j]; } } int d_sz = n*n/d; FORI(pid,0,p){ int max_won = -1; V> ans(n, V (n, 0)); for(auto x0: {0, n-1}){ for(auto y0: {0, n-1}){ int x = x0, y = y0, dx = 0, dy = 1, top = 0, bottom = n-1, left = 0, right = n-1, id = -1; auto districts = ans; if (x == 0 && y == n-1){ dx = 1; dy = 0; } if (x == n-1 && y == n-1){ dx = 0; dy = -1; } if (x == n-1 && y == 0){ dx = -1; dy = 0; } FORI(_,0,n*n){ districts[x][y] = ++id/d_sz + 1; move(1, x, y, dx, dy, top, bottom, left, right); } V> cnt(p, V (d, 0)); FORI(i,0,n){ FORI(j,0,n){ cnt[votes[i][j]-1][districts[i][j]-1]++; } } int won = 0; FORI(di,0,d){ V party_votes; FORI(pi,0,p){ party_votes.push_back({cnt[pi][di], pi}); } sort(ALL(party_votes), greater()); won += party_votes[0].second == pid && party_votes[0].first > party_votes[1].first; } if (won > max_won){ max_won = won; ans = districts; } } } FORI(i,0,n){ FORI(j,0,n){ cout << ans[i][j] << ' '; } cout << endl; } } cin.close(); cout.close(); cerr << "Runtime: " << fixed << time_running() << endl; return 0; }