oj.uz

답안 #123004

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
123004 2019-06-30T01:29:05 Z model_code Necklace (Subtask 1-3) (BOI19_necklace1) C++17
17 / 85
 963 ms 384 KB 
//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

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
5.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 962 ms 376 KB Output is partially correct
2 Partially correct 962 ms 376 KB Output is partially correct
3 Partially correct 962 ms 376 KB Output is partially correct
4 Partially correct 962 ms 376 KB Output is partially correct
5 Partially correct 962 ms 376 KB Output is partially correct

Subtask #2
4.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 962 ms 376 KB Output is partially correct
2 Partially correct 962 ms 376 KB Output is partially correct
3 Partially correct 962 ms 376 KB Output is partially correct
4 Partially correct 962 ms 376 KB Output is partially correct
5 Partially correct 962 ms 376 KB Output is partially correct
6 Partially correct 962 ms 256 KB Output is partially correct
7 Partially correct 962 ms 376 KB Output is partially correct
8 Partially correct 962 ms 376 KB Output is partially correct
9 Partially correct 962 ms 376 KB Output is partially correct
10 Partially correct 962 ms 376 KB Output is partially correct
11 Partially correct 962 ms 364 KB Output is partially correct
12 Partially correct 962 ms 376 KB Output is partially correct

Subtask #3
8.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 962 ms 376 KB Output is partially correct
2 Partially correct 962 ms 376 KB Output is partially correct
3 Partially correct 962 ms 376 KB Output is partially correct
4 Partially correct 962 ms 376 KB Output is partially correct
5 Partially correct 962 ms 376 KB Output is partially correct
6 Partially correct 962 ms 256 KB Output is partially correct
7 Partially correct 962 ms 376 KB Output is partially correct
8 Partially correct 962 ms 376 KB Output is partially correct
9 Partially correct 962 ms 376 KB Output is partially correct
10 Partially correct 962 ms 376 KB Output is partially correct
11 Partially correct 962 ms 364 KB Output is partially correct
12 Partially correct 962 ms 376 KB Output is partially correct
13 Partially correct 962 ms 376 KB Output is partially correct
14 Partially correct 963 ms 380 KB Output is partially correct
15 Partially correct 962 ms 380 KB Output is partially correct
16 Partially correct 962 ms 376 KB Output is partially correct
17 Partially correct 962 ms 384 KB Output is partially correct
18 Partially correct 962 ms 384 KB Output is partially correct
19 Partially correct 962 ms 384 KB Output is partially correct
20 Partially correct 962 ms 376 KB Output is partially correct
21 Partially correct 962 ms 380 KB Output is partially correct