oj.uz

Submission #1011502

# Submission time Handle Problem Language Result Execution time Memory
1011502 2024-06-30T14:28:38 Z MilosMilutinovic Necklace (Subtask 1-3) (BOI19_necklace1) C++14
0 / 85
 1500 ms 265044 KB 
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin >> s;
  string t;
  cin >> t;
  int n = (int) s.size();
  int m = (int) t.size();
  map<string, bool> has;
  map<string, int> pos;
  auto Add = [&](string s, int p) {
    int n = (int) s.size();
    for (int i = 0; i < n; i++) {
      string c = "";
      for (int j = 0; j < n; j++) {
        c += s[(i + j) % n];
        has[c] = true;
        pos[c] = p;
      }
    }
    reverse(s.begin(), s.end());
    for (int i = 0; i < n; i++) {
      string c = "";
      for (int j = 0; j < n; j++) {
        c += s[(i + j) % n];
        has[c] = true;
        pos[c] = p;
      }
    }
  };
  for (int l = 0; l < n; l++) {
    string c = "";
    for (int r = l; r < n; r++) {
      c += s[r];
      Add(c, l);
    }
  }
  array<int, 3> res = {0, 0, 0};
  for (int l = 0; l < n; l++) {
    string c = "";
    for (int r = l; r < n; r++) {
      c += t[r];
      if (has[c]) {
        res = max(res, {(int) c.size(), pos[c], l});
      }
    }
  }
  cout << res[0] << '\n' << res[1] << " " << res[2] << '\n';
  return 0;
}

Compilation message

necklace.cpp: In function 'int main()':
necklace.cpp:13:7: warning: unused variable 'm' [-Wunused-variable]
   13 |   int m = (int) t.size();
      |       ^

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1558 ms 265044 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1558 ms 265044 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1558 ms 265044 KB Time limit exceeded
2 Halted 0 ms 0 KB -