Submission #1264073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264073		rtri	Necklace (Subtask 1-3) (BOI19_necklace1)	C++20	0 / 85	1596 ms	576 KiB

necklace

#include <bits/stdc++.h>
using namespace std;

string sub(string str, int start, int len) {
  int sz = min(len, (int)str.size() - start);
  return str.substr(start, sz) + str.substr(0, max(0, len - sz));
}

string normalize(string str) {
  int best = 0;
  for (int i = 1; i < str.size(); i++) {
    int best_chr, my_chr, idx = 0;
    bool better = false;
    do {
      best_chr = str[(best + i) % str.size()];
      my_chr = str[(idx + i) % str.size()];
      if (my_chr > best_chr)
        better = true;
      idx++;
    } while (best_chr == my_chr);

    if (!better)
      continue;

    best = i;
  }
  return sub(str, best, str.size());
}

int main() {
  string jill, jane;
  cin >> jill >> jane;

  unordered_map<string, int> jane_substr;
  for (int start = 0; start < jane.size(); start++)
    for (int len = 1; len <= jane.size(); len++) {
      string substr = sub(jane, start, len);
      substr = normalize(substr);
      jane_substr.insert({substr, start});
      reverse(substr.begin(), substr.end());
      substr = normalize(substr);
      jane_substr.insert({substr, start});
    }

  int best = 0;
  pair<int, int> bestsol;
  for (int start = 0; start < jill.size(); start++)
    for (int len = best + 1; len <= jill.size(); len++) {
      string substr = sub(jill, start, len);

      if (jane_substr.count(substr)) {
        best = len;
        bestsol = {start, jane_substr[substr]};
      }
    }

  cout << best << endl;
  cout << bestsol.first << " " << bestsol.second << endl;

  return 0;
}

• Subtask 1: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40