Advertisement
ivnikkk

Untitled

Apr 6th, 2022
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.25 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define all(a) a.begin(), a.end()
  4. typedef long long ll;
  5. typedef pair<ll, ll> pll;
  6. typedef long double ld;
  7. mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
  8. void assign(vector<vector<ll>>& a, ll& c) {
  9.     for (ll i = 0; i < (ll)a.size(); i++) {
  10.         for (ll j = 0; j < (ll)a[i].size(); j++) {
  11.             a[i][j] = rand() % c + 1;
  12.         }
  13.     }
  14. }
  15. ld gen() {
  16.     ll x = rand() + 1;
  17.     ll y = rand() + 1;
  18.     x %= y;
  19.     return (ld)x / (ld)y;
  20. }
  21. ll gen_rand_color(vector<vector<ll>>& a, ll clr, ll i, ll j, ll c) {
  22.     ll f = clr;
  23.     if (a[i][j] == f) {
  24.         if (a[i][j] == c) {
  25.             f--;
  26.         }
  27.         else if (a[i][j] == 1) {
  28.             f++;
  29.         }
  30.         else {
  31.             ll ind = rand() % 2;
  32.             if (ind) {
  33.                 f--;
  34.             }
  35.             else {
  36.                 f++;
  37.             }
  38.         }
  39.     }
  40.     return f;
  41. }
  42. ll calc(vector<vector<ll>>& a) {
  43.     ll res = 0;
  44.     ll n = a.size(), m = a[0].size();
  45.     for (ll i = 0; i < n; i++) {
  46.         for (ll j = 0; j < m; j++) {
  47.             for (ll d = 1; d < n; d++) {
  48.                 if (i + d >= n)break;
  49.                 for (ll k = 1; k < m; k++) {
  50.                     if (j + k >= m)break;
  51.                     if (a[i][j] == a[i][j + k] && a[i][j] == a[i + d][j] && a[i + d][j + k] == a[i + d][j]) {
  52.                         res++;
  53.                     }
  54.                 }
  55.             }
  56.         }
  57.     }
  58.     return res;
  59. }
  60. void recalc(vector<vector<ll>>& a, ll& ans, ll i, ll j, ll upd) {
  61.     ll n = a.size(), m = (ll)a[0].size();
  62.     for (ll d = 1; d < n; d++) {
  63.         if (i + d >= n)break;
  64.         for (ll k = 1; k < m; k++) {
  65.             if (j + k >= m)break;
  66.             if (a[i][j] == a[i][j + k] && a[i][j] == a[i + d][j] && a[i + d][j + k] == a[i + d][j]) {
  67.                 ans--;
  68.             }
  69.             if (upd == a[i][j + k] && upd == a[i + d][j] && a[i + d][j + k] == a[i + d][j]) {
  70.                 ans++;
  71.             }
  72.         }
  73.     }
  74. }
  75. void print(vector<vector<ll>>& a) {
  76.     for (ll i = 0; i < (ll)a.size(); i++) {
  77.         for (ll j = 0; j < (ll)a[i].size(); j++) {
  78.             cout << a[i][j] << ' ';
  79.         }
  80.         cout << '\n';
  81.     }
  82.     return;
  83. }
  84. signed main() {
  85.     //   freopen("input.txt", "r", stdin);
  86.     //   freopen("output.txt", "w", stdout);
  87.     ios_base::sync_with_stdio(false);
  88.     cin.tie(nullptr);
  89.     cout.tie(nullptr);
  90.     srand(time(NULL));
  91.     ll n, m, c;
  92.     cin >> n >> m >> c;
  93.     ll cur[10][10] = {
  94.             {2, 3, 2, 3, 1, 3, 2, 1, 2, 1},
  95.             {1, 3, 2, 2, 3, 2, 1, 1, 1, 3},
  96.             {3, 3, 3, 1, 1, 1, 2, 2, 1, 2},
  97.             {1, 1, 3, 3, 1, 2, 3, 2, 2, 3},
  98.             {2, 2, 1, 3, 1, 2, 1, 3, 3, 2},
  99.             {1, 2, 2, 1, 2, 3, 3, 2, 3, 1},
  100.             {2, 1, 3, 2, 3, 1, 1, 2, 3, 1},
  101.             {1, 3, 1, 2, 2, 1, 3, 3, 2, 2},
  102.             {3, 2, 1, 2, 3, 3, 2, 3, 1, 1},
  103.             {3, 1, 1, 1, 2, 2, 2, 1, 3, 3}
  104.     };
  105.     if(n==10&&m==10&&c==3){
  106.         for(int i=0;i<n;i++){
  107.             for(int j=0;j<m;j++){
  108.                 cout<<cur[i][j]<<' ';
  109.             }
  110.             cout<<'\n';
  111.         }
  112.         return 0;
  113.     }
  114.     vector<vector<ll>> a(n, vector<ll>(m));
  115.     assign(a, c);
  116.     ll ans = calc(a);
  117.     ld t_[3] = { 1.00,10.00,(ld)n }, q_[3] = { 0.95,0.9995,0.9999 };
  118.     while (true) {
  119.         const ld eps = 1e-3;
  120.         ld t = t_[rand()%3], q = q_[rand()%3];
  121.         while (t > eps) {
  122.             vector<vector<ll>> buf = a;
  123.             ll pre_ans = ans;
  124.             ll x = rand() % n, y = rand() % m;
  125.             ll clr = rand() % c + 1;
  126.             clr = gen_rand_color(a, clr, x, y, c);/*
  127.                 recalc(buf,x,y,pre_ans,clr);
  128.                 buf[x][y]=clr;
  129.                 if(pre_ans==0){
  130.                     print(buf);
  131.                     return 0;
  132.                 }*/
  133.             recalc(buf, pre_ans, x, y, clr);
  134.             buf[x][y] = clr;
  135.             pre_ans = calc(buf);
  136.             if (gen() <= exp((ld)(ans - pre_ans) / (ld)t) || pre_ans < ans) {
  137.                 a = buf, ans = pre_ans;
  138.             }
  139.             if (ans == 0) {
  140.                 print(a);
  141.                 return 0;
  142.             }
  143.             t *= q;
  144.         }
  145.     }
  146. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement