Submission #657095

#	Time	Username	Problem	Language	Result	Execution time	Memory
657095		bicsi	Necklace (Subtask 1-3) (BOI19_necklace1)	C++14	45 / 85	178 ms	636 KiB

necklace

#include <bits/stdc++.h>

using namespace std;
using ld = long double;

using C = complex<ld>;
const ld EPS = 1e-9;

int main() {
  string s, t; cin >> s >> t;

  mt19937_64 rng(52);
  vector<C> rnd(256);
  for (int i = 0; i < 256; ++i) {
    ld real = 1.0L * rng() / rng.max();
    ld imag = 1.0L * rng() / rng.max();
    rnd[i] = C(real, imag);
    rnd[i] /= abs(rnd[i]);
  }
  
  vector<pair<ld, int>> vs, vt;
  auto check = [&](int len) {
    C eps = polar(1.0, 2.0 * M_PI / len);
    pair<int, int> ans = {-1, -1};
    for (int rev = 0; rev < 2; ++rev) {
      vs.clear(); vt.clear();
      for (int it = 0; it < 2; ++it) {
        C h = 0;
        for (int i = 0; i < (int)s.size(); ++i) {
          h = (h + rnd[s[i]]) * eps;
          if (i >= len - 1) {
            vs.emplace_back(norm(h), i - len + 1);
            h -= rnd[s[i - len + 1]];
          }
        }
        swap(s, t); swap(vs, vt);
      }
      sort(vs.begin(), vs.end());
      sort(vt.begin(), vt.end());
      for (int i = 0, j = 0; i < (int)vs.size(); ++i) {
        while (j < vt.size() && vs[i].first + EPS > vt[j].first) {
          if (abs(vt[j].first - vs[i].first) < EPS) {
            ans.first = vs[i].second;
            ans.second = vt[j].second;
            if (rev) ans.first = s.size() - ans.first - len;
          }
          ++j;
        }
      }
      reverse(s.begin(), s.end());
    }
    return ans;
  };

  int ans = 0, ps = -1, pt = -1;
  int bound = 1;
  while (check(bound).first >= 0) bound *= 2;
  for (int i = bound; i >= bound/2; --i) {
    auto [a, b] = check(i);
    if (a >= 0) {
      ans = i, ps = a, pt = b;
      break;
    }
  }
  cout << ans << endl << ps << " " << pt << endl;

  return 0;
}

Compilation message (stderr)

necklace.cpp: In lambda function:
necklace.cpp:41:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         while (j < vt.size() && vs[i].first + EPS > vt[j].first) {
      |                ~~^~~~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:59:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |     auto [a, b] = check(i);
      |          ^

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