lina_os

Untitled

Apr 29th, 2025
39
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.52 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define ull unsigned long long
  4. #define ld long double
  5.  
  6. using namespace std;
  7.  
  8. ll n,m,k;
  9. vector<vector<vector<ll>>>ps;
  10.  
  11.  
  12. bool can(ll ms) {
  13.     for (ll i=0; i<n-ms+1; i++) {
  14.         for (ll j=0; j<m-ms+1; j++) {
  15.             ll x=i, y=j, xx=x+ms-1,yy=y+ms-1;
  16.             x++; y++; xx++; yy++;
  17.  
  18.             vector<ll>f(26);
  19.             for (int l=0; l<26; l++) {
  20.                 f[l]=ps[xx][yy][l]+ps[x-1][y-1][l]-ps[x-1][yy][l]-ps[xx][y-1][l];
  21.  
  22.             }
  23.             sort(f.begin(), f.end());
  24.             ll kk = 26 - (upper_bound(f.begin(), f.end(), 0)-f.begin());
  25.             if (kk==k) return true;
  26.         }
  27.     }
  28.     return false;
  29. }
  30.  
  31. pair<ll,ll> solve(ll ms) {
  32.     for (ll i=0; i<n-ms+1; i++) {
  33.         for (ll j=0; j<m-ms+1; j++) {
  34.             ll x=i, y=j, xx=x+ms-1,yy=y+ms-1;
  35.             x++; y++; xx++; yy++;
  36.  
  37.             vector<ll>f(26);
  38.             for (int l=0; l<26; l++) {
  39.                 f[l]=ps[xx][yy][l]+ps[x-1][y-1][l]-ps[x-1][yy][l]-ps[xx][y-1][l];
  40.  
  41.             }
  42.             sort(f.begin(), f.end());
  43.             ll kk = 26 - (upper_bound(f.begin(), f.end(), 0)-f.begin());
  44.             if (kk==k) return {x+1,y+1};
  45.         }
  46.     }
  47. }
  48.  
  49. int main() {
  50.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  51.     cin >> n >> m >> k;
  52.     vector<vector<char>>v(n, vector<char>(m));
  53.     ps.resize(n + 1, vector<vector<ll>>(m + 1, vector<ll>(26)));
  54.     for (auto &i:v)
  55.         for (auto &j:i)
  56.             cin >> j;
  57.  
  58.     // prefix frequency
  59.     for (int i=1; i<=n; i++) {
  60.         for (int j=1; j<=m; j++) {
  61.             for (int l=0; l<26; l++) {
  62.                 ps[i][j][l]=ps[i-1][j][l]+ps[i][j-1][l]-ps[i-1][j-1][l];
  63.             }
  64.             ps[i][j][v[i-1][j-1]-'A']++;
  65.         }
  66.     }
  67.  
  68. //    for (int i = 1; i <= n; i++) {
  69. //        for (int j = 1; j <= m; j++) {
  70. //            cout << "(";
  71. //            for (int l = 0; l < 26; l++) {
  72. //                cout << ps[i][j][l] << " ";
  73. //            }
  74. //            cout << endl;
  75. //        }
  76. //        cout << ") ";
  77. //        cout << endl;
  78. //    }
  79.     //binary search on minimum side length
  80.     ll l=1,r=min(n,m),mid;
  81.     while (l<=r) {
  82.         mid=(l+r)/2;
  83.         if (can(mid)) {
  84.             if (mid==1 || !can(mid-1)) {
  85.                 cout << mid << endl << solve(mid).first << ' ' << solve(mid).second << endl;
  86.                 return 0;
  87.             }
  88.             else r=mid-1;
  89.         }
  90.         else l=mid+1;
  91.     }
  92.     cout << -1 << endl;
  93.     return 0;
  94. }
Advertisement
Add Comment
Please, Sign In to add comment