Advertisement
K_Y_M_bl_C

Untitled

Nov 1st, 2017
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.46 KB | None | 0 0
  1. int solve()
  2. {
  3.     int n, m, k;
  4.     scanf("%d %d %d", &n, &m, &k);
  5.     char a[n][m + 1];
  6.     for (int i = 0; i < n; ++i)
  7.     {
  8.         scanf(" %s", a[i]);
  9.     }
  10.     vector<pii> swaps(m / 2, mk(0, 2));
  11.     int ans = 0;
  12.     pii solo = mk(0, 0);
  13.     if (m & 1)
  14.     {
  15.         solo = mk(0, 1);
  16.         for (int i = 0; i < n; ++i)
  17.         {
  18.             if (a[i][m / 2] != a[n - i - 1][m / 2])
  19.                 ++solo.X;
  20.         }
  21.     }
  22.     for (int i = 0; i < n; ++i)
  23.     {
  24.         pii cur = mk(0, 2);
  25.         int ri = n - i - 1;
  26.         for (int j = 0; j < m / 2; ++j)
  27.         {
  28.             int rj = m - j - 1;
  29.             if (a[i][j] != a[i][rj])
  30.                 ++ans;
  31.             if (i < n / 2)
  32.             {
  33.                 char c1 = a[i][j];
  34.                 char c2 = a[i][rj];
  35.                 char c3 = a[ri][j];
  36.                 char c4 = a[ri][rj];
  37.                 //c1 c2
  38.                 //c3 c4
  39.                 //c1 == c2 c3 == c4
  40.                 if (c1 == c2 && c3 == c4)
  41.                 {
  42.                     if (c1 == c3)
  43.                         swaps[j].X += 0;
  44.                     else
  45.                         swaps[j].X += 2;
  46.                 }
  47.                 if (c1 == c2 && c3 != c4)
  48.                 {
  49.                     if (c3 != c1 && c3 != c2 && c4 != c1 && c4 != c2)
  50.                         swaps[j].X += 1;
  51.                 }
  52.                 if (c1 != c2 && c3 == c4)
  53.                 {
  54.                     if (c1 != c3 && c1 != c4 && c2 != c3 && c2 != c4)
  55.                         swaps[j].X += 1;
  56.                 }
  57.                 if (c1 != c2 && c3 != c4)
  58.                 {
  59.                     if (c1 != c3 && c1 != c4 && c2 != c3 && c2 != c4)
  60.                         swaps[j].X += 1;
  61.                 }
  62.             }
  63.         }
  64.     }
  65.     sort(all(swaps), [&](pii x, pii y)
  66.     {
  67.         return x.X * y.Y < y.X * x.Y;
  68.     });
  69.     int cr = 0;
  70.     for (auto x : swaps)
  71.     {
  72.         if (cr >= k)
  73.             break;
  74.         if (solo.Y)
  75.         {
  76.             if (solo.Y + cr >= k && cr + x.Y >= k)
  77.             {
  78.                 ans += min(x.X, solo.X);
  79.                 break;
  80.             }
  81.         }
  82.         cr += x.Y;
  83.         ans += x.X;
  84.     }
  85.     printf("%d\n", ans);
  86.     return 0;
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement