fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define TASK "BOARDGAME"
  5. #define all(x) (x).begin(), (x).end()
  6.  
  7. typedef long long ll;
  8. typedef pair<int, int> ii;
  9.  
  10. const int MAX_M = 2e5;
  11. const int MAX_N = 2e5;
  12. const int MAX_Q = 10;
  13. const int MOD = (int)1e9 + 7;
  14.  
  15. template <class X, class Y>
  16. bool maximize(X& x, const Y& y) {
  17.     if (x >= y) return false;
  18.     x = y;
  19.     return true;
  20. };
  21. template <class X, class Y>
  22. bool minimize(X& x, const Y& y) {
  23.     if (x <= y) return false;
  24.     x = y;
  25.     return true;
  26. };
  27.  
  28. int m, n, q;
  29. string queries[MAX_Q + 5];
  30. string a[MAX_M + 5];
  31.  
  32. namespace SUBTASK_1 {
  33.     const int M = MAX_M;
  34.     const int N = 5e6;
  35.  
  36.     int z[N + 5];
  37.  
  38.     bool checkSubtask() {
  39.         return 1LL * m * n < m + n;
  40.     };
  41.  
  42.     void calcZFunction(const string& s) {
  43.         z[0] = 0;
  44.         int n = s.size();
  45.         for (int i = 1, l = 0, r = 0; i < n; i++) {
  46.             if (i < r) {
  47.                 z[i] = min(z[i - l], r - i);
  48.             };
  49.  
  50.             while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
  51.  
  52.             if (i + z[i] > r) {
  53.                 l = i;
  54.                 r = i + z[i];
  55.             };
  56.         };
  57.     };
  58.  
  59.     void Solve() {
  60.         string board;
  61.         for (int i = 1; i <= m; i++)
  62.             for (int j = 1; j <= n; j++) board += a[i][j];
  63.  
  64.         for (int i = 1; i <= q; i++) {
  65.             string period;
  66.             for (int k = 0; k < m * n; k++) {
  67.                 period += queries[i][k % queries[i].size()];
  68.             };
  69.  
  70.             string st = period + '#' + board;
  71.             calcZFunction(st);
  72.  
  73.             int res = 0;
  74.             for (int j = m * n + 1; j < st.size(); j++) {
  75.                 int k = z[j];
  76.                 int len = (k / queries[i].size()) * queries[i].size();
  77.                 maximize(res, len);
  78.             };
  79.  
  80.             string boardRev = board;
  81.             reverse(all(boardRev));
  82.  
  83.             string stRev = period + '#' + boardRev;
  84.             calcZFunction(stRev);
  85.  
  86.             for (int j = m * n + 1; j < stRev.size(); j++) {
  87.                 int k = z[j];
  88.                 int len = (k / queries[i].size()) * queries[i].size();
  89.                 maximize(res, len);
  90.             };
  91.  
  92.             cout << res << ' ';
  93.         };
  94.  
  95.         cout << '\n';
  96.     };
  97. };  // namespace SUBTASK_1
  98.  
  99. void solve() {
  100.     cin >> m >> n >> q;
  101.     for (int i = 1; i <= m; i++) {
  102.         cin >> a[i];
  103.         a[i] = " " + a[i];
  104.     };
  105.  
  106.     for (int i = 1; i <= q; i++) cin >> queries[i];
  107.  
  108.     SUBTASK_1::Solve();
  109. };
  110.  
  111. int main() {
  112.     ios_base::sync_with_stdio(0);
  113.     cin.tie(0);
  114.     if (fopen(TASK ".INP", "r")) {
  115.         freopen(TASK ".INP", "r", stdin);
  116.         freopen(TASK ".OUT", "w", stdout);
  117.     };
  118.  
  119.     int t;
  120.     cin >> t;
  121.     while (t--) solve();
  122. };
Success #stdin #stdout 0.01s 10484KB
comments (?)
stdin 
Standard input is empty
stdout
https://ideone.com/1YTkzZ
language:
C++14 (gcc 8.3)
created:
12 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!