Advertisement
Guest User

Untitled

a guest
Nov 18th, 2024
166
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.85 KB | None | 0 0
  1. // clang-format off
  2. #include<bits/stdc++.h>
  3.    
  4. using namespace std;
  5.    
  6. #ifdef LOCAL
  7. #include "deb/debug.h"
  8. #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  9. #else  
  10. #define debug(...) 42
  11. #endif
  12.    
  13. #define int long long
  14.    
  15. typedef unsigned long long ull;
  16. typedef long double ld;
  17.      
  18. #define ff first
  19. #define ss second
  20.  
  21. const int K = 5e4;
  22. const int MODR = 1e5;
  23.  
  24. mt19937 rnd(time(0));
  25.  
  26. int func(int n, int m, vector< vector<int> > &v) {
  27.     int cnt = 0;
  28.     for (int x1 = 0; x1 < n; x1++) {
  29.         for (int x2 = x1 + 1; x2 < n; x2++) {
  30.             for (int y1 = 0; y1 < m; y1++) {
  31.                 for (int y2 = y1 + 1; y2 < m; y2++) {
  32.                     if (v[x1][y1] == v[x2][y1] && v[x1][y1] == v[x1][y2] && v[x1][y1] == v[x2][y2])
  33.                         cnt++;
  34.                 }
  35.             }
  36.         }
  37.     }
  38.     return cnt;
  39. }
  40.  
  41. ld prob() {
  42.     int x = rnd() % MODR;
  43.     return (ld)x / (ld)MODR;
  44. }
  45.  
  46. void solve() {
  47.     int n, m, c;
  48.     cin >> n >> m >> c;
  49.     vector< vector<int> > v(n, vector<int>(m));
  50.     for (int i = 0; i < n; i++) {
  51.         for (int j = 0; j < m; j++) {
  52.             v[i][j] = rnd() % c + 1;
  53.         }
  54.     }
  55.     if (c == 3) {
  56.         vector< vector<int> > tr(10, vector<int>(10));
  57.         tr[0] = {1, 2, 2, 3, 2, 1, 1, 3, 3, 3};
  58.         tr[1] = {3, 1, 2, 2, 1, 3, 1, 1, 3, 2};
  59.         tr[2] = {2, 2, 1, 1, 3, 1, 3, 1, 3, 2};
  60.         tr[3] = {2, 3, 2, 1, 3, 2, 1, 3, 2, 1};
  61.         tr[4] = {1, 2, 3, 2, 3, 2, 2, 1, 1, 3};
  62.         tr[5] = {1, 2, 1, 3, 1, 3, 3, 2, 2, 1};
  63.         tr[6] = {3, 1, 2, 3, 3, 1, 2, 2, 1, 1};
  64.         tr[7] = {3, 3, 3, 1, 1, 2, 3, 2, 1, 2};
  65.         tr[8] = {2, 3, 1, 2, 2, 3, 1, 2, 1, 3};
  66.         tr[9] = {1, 1, 3, 1, 2, 3, 2, 3, 2, 2};
  67.         for (int i = 0; i < n; i++) {
  68.             for (int j = 0; j < m; j++) {
  69.                 cout << tr[i][j] << " \n"[j == m - 1];
  70.             }
  71.         }
  72.         return;
  73.     }
  74.     int ans = func(n, m, v);
  75.     ld t = 1;
  76.     for (int i = 0; i < K && ans; i++) {
  77.         t *= 0.99;
  78.         if (t < 0.001)
  79.             t = 1;
  80.         vector< vector<int> > u = v;
  81.         int x = rnd() % n;
  82.         int y = rnd() % m;
  83.         int p = rnd() % c + 1;
  84.         while (p == u[x][y])
  85.             p = rnd() % c + 1;
  86.         u[x][y] = p;
  87.         int cur = func(n, m, u);
  88.         if (cur < ans) {
  89.             ans = cur;
  90.             v.swap(u);
  91.         } else if (prob() < exp((ans - cur) / t)) {
  92.             ans = cur;
  93.             v.swap(u);
  94.         }
  95.     }
  96.     debug(func(n, m, v));
  97.     for (int i = 0; i < n; i++) {
  98.         for (int j = 0; j < m; j++) {
  99.             cout << v[i][j] << ' ';
  100.         }
  101.         cout << '\n';
  102.     }
  103. }
  104.  
  105. signed main() {
  106.     ios_base::sync_with_stdio(false);
  107.     cin.tie(0);
  108.     int _ = 1;
  109.     // cin >> _;
  110.     for (;_; --_) {
  111.         solve();
  112.     }
  113.     return 0;
  114. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement