Submission #657398

#	Time	Username	Problem	Language	Result	Execution time	Memory
657398		bicsi	Necklace (Subtask 4) (BOI19_necklace4)	C++14	0 / 15	394 ms	620 KiB

necklace

#include <bits/stdc++.h>

using namespace std;
using ld = long double;
const ld EPS = 6e-11;

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

  mt19937_64 rng(72);
  vector<complex<ld>> 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] = {real, imag};
  }
  
  vector<pair<ld, int>> vs, vt;
  auto check = [&](int len) {
    complex<ld> eps = polar(1.0L, 2.0L * 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) {
        complex<ld> 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]];
            if (i % len == 0) {
              h = 0;
              for (int j = i - len + 2; j <= i; ++j)
                h = (h + rnd[s[j]]) * eps;
            }
          }
          
        }
        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 + 20; i >= max(1, bound/2 - 20); --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:44: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]
   44 |         while (j < vt.size() && vs[i].first + EPS > vt[j].first) {
      |                ~~^~~~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:62:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |     auto [a, b] = check(i);
      |          ^

• Subtask 1: 0 / 15