fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. // #define int long long int
  5. #define ld long double
  6. #define all(x) x.begin(), x.end()
  7. #define sortall(x) sort(all(x))
  8. #define endl '\n'
  9. #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  10. template<class T>
  11. void printC (T Collection)
  12. {
  13.     for (auto&i:Collection)
  14.         cout << i << " \n";
  15.     cout << '\n';
  16. }
  17.  
  18. /*
  19.  * Think twice, code once
  20.  * Think of different approaches to tackle a problem: write them down.
  21.  * Think of different views of the problem. don't look from only one side.
  22.  * don't get stuck in one approach.
  23.  * common mistakes: - over_flow
  24.  *                  - out_of_bound index
  25.  *                  - infinite loop
  26.  *                  - corner cases
  27.  *                  - duplication counting.
  28. */
  29. void solve()
  30. {
  31.     int r, c, s;
  32.     cin >> r >> c >> s;
  33.     vector<vector<char>> v(r,vector<char>(c));
  34.     for (auto&i:v)
  35.         for (auto&j:i)
  36.             cin >> j;
  37.     vector<vector<vector<int>>> prefix(r+1,vector<vector<int>>(c+1,vector<int>(26)));
  38.     for (int i = 0; i < r; ++i)
  39.         for (int j = 0; j < c; ++j)
  40.             prefix[i+1][j+1][v[i][j]-'A']++;
  41.  
  42.     for (int i = 0; i < r; ++i)
  43.         for (int j = 0; j < c; ++j)
  44.             for (int k = 0; k < 26; ++k)
  45.                 prefix[i+1][j+1][k] += prefix[i+1][j][k];
  46.  
  47.     for (int j = 0; j < c; ++j)
  48.         for (int i = 0; i < r; ++i)
  49.             for (int k = 0; k < 26; ++k)
  50.                 prefix[i+1][j+1][k] += prefix[i][j+1][k];
  51.  
  52.     pair<int,pair<int,int>> ans = {INT_MAX,{INT_MAX,INT_MAX}};
  53.     for (int i = 1; i <= r; ++i)
  54.     {
  55.         for (int j = 1; j <= c; ++j)
  56.         {
  57.             int l1 = i, r1 = j, l2 = i+min(r-i, c-j), r2 = j+min(r-i, c-j);
  58.             while (l1 <= l2 && r1 <= r2)
  59.             {
  60.                 int mid1 = (l1+l2)>>1;
  61.                 int mid2 = (r1+r2)>>1;
  62.                 int cnt = 0;
  63.                 for (int k = 0; k < 26; ++k)
  64.                 {
  65.                     if (prefix[mid1][mid2][k]-prefix[i-1][mid2][k]-prefix[mid1][j-1][k]+prefix[i-1][j-1][k] > 0)
  66.                         cnt++;
  67.                 }
  68.                 if (cnt >= s)
  69.                 {
  70.                     if (ans.first > mid1-i+1)
  71.                     {
  72.                         ans.first = mid1-i+1;
  73.                         ans.second.first = i;
  74.                         ans.second.second = j;
  75.                     }else if (ans.first == mid1-i+1)
  76.                     {
  77.                         if (ans.second.first > i)
  78.                         {
  79.                             ans.second.first = i;
  80.                             ans.second.second = j;
  81.                         }else if (ans.second.first == i)
  82.                         {
  83.                             if (ans.second.second > j)
  84.                             {
  85.                                 ans.second.second = j;
  86.                             }
  87.                         }
  88.                     }
  89.                     l2 = mid1 - 1;
  90.                     r2 = mid2 - 1;
  91.                 }else
  92.                 {
  93.                     l1 = mid1 + 1;
  94.                     r1 = mid2 + 1;
  95.                 }
  96.             }
  97.         }
  98.     }
  99.     if (ans.first == INT_MAX)
  100.         cout << -1;
  101.     else
  102.     {
  103.         cout << ans.first << '\n';
  104.         cout << ans.second.first << ' ' << ans.second.second;
  105.     }
  106. }
  107.  
  108. int32_t main()
  109. {
  110.     // #ifndef ONLINE_JUDGE
  111.     //     freopen("input.txt", "r", stdin);
  112.     //     freopen("output.txt", "w", stdout);
  113.     //     freopen("Errors.txt", "w", stderr);
  114.     // #endif
  115.     fast
  116.     int t = 1;
  117.     // cin >> t;
  118.     while (t--)
  119.     {
  120.         solve();
  121.         if (t) cout << '\n';
  122.     }
  123.     cout << '\n';
  124.     return 0;
  125. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/EMxLXV
language:
C++14 (gcc 8.3)
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!