제출 #123003

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
123003		model_code	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	53 / 85	962 ms	504 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;
#ifdef LOC
  int cnt = 0;
  ll ops = 0;
#endif
  while (clock() < c_end) {
#ifdef LOC
    ++cnt;
#endif
    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]) {
#ifdef LOC
      ++ops;
#endif
      --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]]) {
#ifdef LOC
      ++ops;
#endif
      ++r[0];
      ++r[1];
    }
    int len = r[0] - l[0];
    if (2 * len <= res) continue;
    if (len > res) {
      res = len;
#ifdef LOC
      fprintf(stderr, "str = %d\n", res);
      fprintf(stderr, "cnt = %d\n", cnt);
      fprintf(stderr, "ops = %lld\n", ops);
#endif
      loc[0] = l[0];
      loc[1] = l[1];
    }
    for (int i = 0; i < 2; ++i) {
      for (int j = min(len, min(n[i] - r[i], l[!i])); j > res - len; --j) {
        int tl[2];
        tl[i] = r[i];
        tl[!i] = l[!i] - j;
        bool err = false;
        for (int k = 0; k < j; ++k, ++tl[0], ++tl[1]) {
#ifdef LOC
          ++ops;
#endif
          if (s[0][tl[0]] != s[1][tl[1]]) {
            err = true;
            break;
          }
        }
        if (!err) {
          res = len + j;
#ifdef LOC
          fprintf(stderr, "neck = %d\n", res);
          fprintf(stderr, "cnt = %d\n", cnt);
          fprintf(stderr, "ops = %lld\n", ops);
#endif
          loc[i] = l[i];
          loc[!i] = l[!i] - j;
        }
      }
    }
  }
#ifdef LOC
  fprintf(stderr, "cnt = %d\n", cnt);
  fprintf(stderr, "ops = %lld\n", ops);
#endif
  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;
}

컴파일 시 표준 에러 (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:126:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", buf);
   ~~~~~^~~~~~~~~~~
necklace.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", buf);
   ~~~~~^~~~~~~~~~~

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