Submission #156337

#	Time	Username	Problem	Language	Result	Execution time	Memory
156337		ryansee	Necklace (Subtask 4) (BOI19_necklace4)	C++14	3 / 15	963 ms	520 KiB

necklace

//randomized: time expected O(n^3)

#pragma GCC optimize("Ofast")

#include <algorithm>
#include <chrono>
#include <ctime>
#include <iostream>
#include <random>
#include <string>
#include <vector>

using namespace std;
typedef long long ll;

mt19937 gen;
clock_t c_start;

int solve_noflip(string &a, string &b, clock_t c_end, int *loc) {
  string s[2] = {a, b};
  int n[2] = {a.size(), b.size()};
  int l[2];
  int r[2];
  int res = 0;
  while (clock() < c_end) {
    for (int i = 0; i < 2; ++i) {
      l[i] = gen() % n[i];
      r[i] = l[i];
    }
    if (2 * (min(l[0], l[1]) + min(n[0] - r[0], n[1] - r[1])) <= res) continue;
    while (min(l[0], l[1]) > 0 && s[0][l[0] - 1] == s[1][l[1] - 1]) {
      --l[0];
      --l[1];
    }
    if (2 * (r[0] - l[0] + min(n[0] - r[0], n[1] - r[1])) <= res) continue;
    while (r[0] < n[0] && r[1] < n[1] && s[0][r[0]] == s[1][r[1]]) {
      ++r[0];
      ++r[1];
    }
    int len = r[0] - l[0];
    if (len > res) {
      res = len;
      loc[0] = l[0];
      loc[1] = l[1];
    }
  }
  return res;
}

int solve(string &s, string &t, int *loc) {
  int loc_noflip[2];
  int res = solve_noflip(s, t, c_start + CLOCKS_PER_SEC * 48 / 100, loc_noflip);
  reverse(t.begin(), t.end());
  int loc_flip[2];
  int res_flip = solve_noflip(s, t, c_start + CLOCKS_PER_SEC * 96 / 100, loc_flip);
  if (res_flip > res) {
    res = res_flip;
    loc[0] = loc_flip[0];
    loc[1] = (int)t.size() - loc_flip[1] - res;
  } else {
    for (int i = 0; i < 2; ++i) loc[i] = loc_noflip[i];
  }
  return res;
}
const int nmax = 3e3+5;

char buf[nmax];

int main() {
  c_start = std::clock();

  ll seed = static_cast< ll >(std::chrono::system_clock::now().time_since_epoch().count());
  gen = mt19937(seed);
  gen.discard(gen.state_size);

  scanf("%s", buf);
  string s(buf);
  scanf("%s", buf);
  string t(buf);
  int loc[2];
  int res = solve(s, t, loc);
  cout << res << '\n';
  if (res) {
    cout << loc[0] << ' ' << loc[1] << '\n';
  }
  return 0;
}

Compilation message (stderr)

necklace.cpp: In function 'int solve_noflip(std::__cxx11::string&, std::__cxx11::string&, clock_t, int*)':
necklace.cpp:21:21: warning: narrowing conversion of '(& a)->std::__cxx11::basic_string<char>::size()' from 'std::__cxx11::basic_string<char>::size_type {aka long unsigned int}' to 'int' inside { } [-Wnarrowing]
   int n[2] = {a.size(), b.size()};
               ~~~~~~^~
necklace.cpp:21:31: warning: narrowing conversion of '(& b)->std::__cxx11::basic_string<char>::size()' from 'std::__cxx11::basic_string<char>::size_type {aka long unsigned int}' to 'int' inside { } [-Wnarrowing]
   int n[2] = {a.size(), b.size()};
                         ~~~~~~^~
necklace.cpp: In function 'int main()':
necklace.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", buf);
   ~~~~~^~~~~~~~~~~
necklace.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", buf);
   ~~~~~^~~~~~~~~~~

• Subtask 1: 3 / 15