fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <cstdint>
  3. #include <iomanip>
  4. #define PowerUp ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(0);
  5. #define BattleMode ll t;cin>>t;while(t--)
  6. #define Thor solve();
  7. #define Thunder if(t>0){cout<<line;}
  8. #define ll long long
  9. #define line "\n"
  10. #define line3 cout<<line;
  11. #define stop string abnmj; cin>>abnmj;
  12. #define tap "\t"
  13. #define loop(end,char) for(ll char=0;char<end;char++)
  14. #define loopr(end,char) for(int char=end-1;char>=0;char--)
  15. #define arrin(name) loop(name.size(),p){cin>>name[p];}
  16. #define print(name) for(auto ik:name){cout<<ik<<" ";}
  17. #define print2(name) for(auto ik:name){cout<<ik.first<<" "<<ik.second<<line;}
  18. #define temple template<typename t,typename v>
  19. #define all(x) x.begin(),x.end()
  20. #define allr(x) x.rbegin(),x.rend()
  21. using namespace std;
  22. const double pi = acos(-1);
  23. const ll MOD = 1e9 + 7;
  24. const double EPS = 1e-7;
  25. int n, m, k;
  26. char a[1005][1005];
  27. vector<vector<vector<int> > > prefix(1005, vector<vector<int> >(1005, vector<int>(26,0)));
  28.  
  29. int distinct_values(vector<int> v)
  30. {
  31.     int counter = 0;
  32.     for (auto it: v)
  33.     {
  34.         if (it > 0)
  35.             counter++;
  36.     }
  37.     return counter;
  38. }
  39.  
  40. void print_frequancy(vector<int> freq)
  41. {
  42.     for (int i = 0; i < 26; i++)
  43.     {
  44.         if (freq[i] > 0)
  45.         {
  46.             cout << static_cast<char>(i + 'A') << " " << freq[i] << line;
  47.         }
  48.     }
  49. }
  50.  
  51. pair<int,int> check_window(const int sz)
  52. {
  53.     //initiate fixed_size window
  54.     vector<int> freq(26, 0);
  55.     vector<pair<int, int> > res;
  56.     for (int k = 0; k < 26; k++)
  57.         freq[k] = prefix[sz][sz][k] - prefix[0][sz][k] - prefix[sz][0][k] + prefix[0][0][k];
  58.     int sum;
  59.     for (int i = sz; i <= n; i++)
  60.     {
  61.         sum = distinct_values(freq);
  62.         if (sum >= k)
  63.             res.push_back({i - sz+1, 1});
  64.         vector<int> temp(all(freq));
  65.         for (int j = sz; j < m; j++)
  66.         {
  67.  
  68.             for (int k = 0; k < 26; k++)
  69.             {
  70.                 temp[k] += prefix[i][j + 1][k] + prefix[i - sz][j][k] - prefix[i][j][k] - prefix[i - sz][j + 1][k];
  71.                 temp[k] -= prefix[i][j - sz + 1][k] + prefix[i - sz][j - sz][k] - prefix[i][j - sz][k] - prefix[i - sz][j - sz + 1][k];
  72.             }
  73.             sum = distinct_values(temp);
  74.             if (sum >= k)
  75.                 res.push_back({i - sz + 1, j - sz + 2});
  76.         }
  77.         if (i >= n)
  78.             break;
  79.         for (int k = 0; k < 26; k++)
  80.         {
  81.             freq[k] += prefix[i + 1][sz][k] + prefix[i][0][k] - prefix[i + 1][0][k] - prefix[i][sz][k];
  82.             freq[k] -= prefix[i - sz + 1][sz][k] + prefix[i - sz][0][k] - prefix[i - sz + 1][0][k] - prefix[i - sz][sz][k];
  83.         }
  84.     }
  85.     if (!res.empty())
  86.         return res.front();
  87.     return {-1, -1};
  88. }
  89.  
  90. void solve()
  91. {
  92.     cin >> n >> m >> k;
  93.     for (int i = 1; i <= n; i++)
  94.     {
  95.         for (int j = 1; j <= m; j++)
  96.         {
  97.             cin >> a[i][j];
  98.         }
  99.     }
  100.     for (int i = 1; i <= n; i++)
  101.     {
  102.         for (int j = 1; j <= m; j++)
  103.         {
  104.             for (int k = 0; k < 26; k++)
  105.             {
  106.                 prefix[i][j][k] = prefix[i - 1][j][k] + prefix[i][j - 1][k] - prefix[i - 1][j - 1][k];
  107.             }
  108.             prefix[i][j][a[i][j] - 'A']++;
  109.         }
  110.     }
  111.     int left = 1, right = min(m, n) + 1;
  112.     pair<int, int> NO = {-1, -1};
  113.  
  114.     while (left < right)
  115.     {
  116.         int mid = (right - left) / 2 + left;
  117.         pair<int, int> temp = check_window(mid);
  118.         if (temp != NO)
  119.             right = mid;
  120.         else
  121.             left = mid + 1;
  122.     }
  123.  
  124.     pair<int, int> result = check_window(right);
  125.     if (result == NO)
  126.         cout << -1;
  127.     else
  128.     {
  129.         cout << right << line << result.first  << " " << result.second  << line;
  130.     }
  131. }
  132.  
  133. int main()
  134. {
  135. #ifndef ONLINE_JUDGE
  136.     freopen("input.txt", "r", stdin);
  137.     freopen("output.txt", "w", stdout);
  138.     freopen("error.txt", "w", stderr);
  139. #endif
  140.     PowerUp
  141.     Thor
  142. }
  143.  
Success #stdin #stdout 0.12s 137888KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/Fu2vJN
language:
C++14 (clang 8.0)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!