oj.uz

답안 #656145

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
656145 2022-11-06T11:28:09 Z 600Mihnea Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 1500 ms 807712 KB 
bool home = 0;
bool verbose = 1;

#include <bits/stdc++.h>

using namespace std;

mt19937 rng(7777);

typedef double ld;

const ld PI = 3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196442881097566593344612847564823378678316527120190914;
using cd = complex<ld>;

int getlog2(int x) {
  if (x == 1) return 0;
  return 1 + getlog2(x / 2);
}

void fft(vector<cd>& a, bool inv) {
  int n = (int)a.size(), k = getlog2(n);

  for (int i = 0; i < n; i++) {
    int j = 0;
    for (int bit = 0; bit < k; bit++) {
      if (i & (1 << bit)) {
        j += (1 << (k - 1 - bit));
      }
    }
    if (i < j) {
      swap(a[i], a[j]);
    }
  }

  for (int l = 2; l <= n; l *= 2) {
    ld ang = 2 * PI / (ld)l;
    if (inv) ang *= -1;
    cd mlt(cos(ang), sin(ang));
    for (int i = 0; i < n; i += l) {
      cd cur(1);
      for (int j = 0; j < l / 2; j++) {
        cd x = a[i + j];
        cd y = a[i + l / 2 + j] * cur;
        a[i + j] = x + y;
        a[i + l / 2 + j] = x - y;
        cur *= mlt;
      }
    }
  }

  if (inv) {
    for (auto& x : a) {
      x /= n;
    }
  }
}

void conv_smart(vector<cd> a, vector<cd> b, vector<cd> &sol) {
  int n = 1;
  while (n <= (int)a.size() + (int)b.size()) n *= 2;

  a.resize(n, 0);
  b.resize(n, 0);
  fft(a, 0);
  fft(b, 0);

  for (int i = 0; i < n; i++) {
    a[i] *= b[i];
  }
  fft(a, 1);
  sol.clear();

  for (int i = 0; i < n; i++) {
    sol.push_back(a[i]);
  }
}

ld values[26];

const ld eps = 1e-6;

vector<cd> lol, cs, a;
vector<cd> reta, retb;

void place(string s, int len, vector<ld> &sol) {
  sol.clear();
  int n = (int) s.size();
  if (len > n) {
    return;
  }
  ld ang = 2 * PI / len;
  cd c(cos(ang), sin(ang));
  cs.resize(len);
  a.resize(n);
  cs[0] = 1;
  for (int i = 1; i < len; i++) {
    cs[i] = cs[i - 1] * c;
  }
  for (int i = 0; i < n; i++) {
    a[i] = values[s[i] - 'a'];
  }
  sol.resize(n - len + 1);
  conv_smart(cs, a, lol);
  for (int i = 0; i < n - len + 1; i++) {
    sol[i] = norm(lol[i + len - 1]);
  }
}

string s, t;
vector<ld> norms_s, norms_t;

bool isok(int len) {
  if (len > (int) s.size() || len > (int) t.size()) {
    return 0;
  }
  int n = (int) s.size() - len + 1;
  int m = (int) t.size() - len + 1;
  norms_s.resize(n);
  norms_t.resize(m);
  for (int i = 0; i < n; i++) {
    norms_s[i] = norm(reta[(len - 1) * ((int) s.size() + 2) + i]);
  }
  for (int i = 0; i < m; i++) {
    norms_t[i] = norm(retb[(len - 1) * ((int) t.size() + 2) + i]);
  }
  sort(norms_s.begin(), norms_s.end());
  sort(norms_t.begin(), norms_t.end());
  int j = 0;
  for (int i = 0; i < n; i++) {
    while (j < m && norms_t[j] < norms_s[i]) {
      j++;
    }
    if (0 <= j && j < m && abs(norms_s[i] - norms_t[j]) < eps) {
      return 1;
    }
    if (0 <= j - 1 && j - 1 < m && abs(norms_s[i] - norms_t[j - 1]) < eps) {
      return 1;
    }
  }
  return 0;
}

void print(int len) {
  int n = (int) s.size() - len + 1;
  int m = (int) t.size() - len + 1;
  norms_s.resize(n);
  norms_t.resize(m);
  for (int i = 0; i < n; i++) {
    norms_s[i] = norm(reta[(len - 1) * ((int) s.size() + 2) + i]);
  }
  for (int i = 0; i < m; i++) {
    norms_t[i] = norm(retb[(len - 1) * ((int) t.size() + 2) + i]);
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (abs(norms_s[i] - norms_t[j]) < eps) {
        cout << i << " " << j << "\n";
        exit(0);
      }
    }
  }
}

vector<cd> cur;

void add(vector<cd> &v) {
  for (auto &x : v) {
    cur.push_back(x);
  }
}

int main() {
  for (int x = 0; x < 26; x++) {
    values[x] = cos(rng()) * 10;
  }
  if (!home) {
    verbose = 0;
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
  }
  if (home) {
    verbose = 1;
    freopen ("___input___.txt", "r", stdin);
  }

  cin >> s >> t;
  int n = (int) s.size(), m = (int) t.size();
  for (int len = 1; len <= n; len++) {
    vector<cd> x(len);
    ld ang = 2 * PI / len;
    cd c(cos(ang), sin(ang));
    x[0] = 1;
    for (int i = 1; i < len; i++) {
      x[i] = x[i - 1] * c;
    }
    for (int i = 0; i <= n - len; i++) {
      x.push_back(0);
    }
    add(x);
  }

  {
    a.resize(n);
    for (int i = 0; i < n; i++) {
      a[i] = values[s[i] - 'a'];
    }
    conv_smart(a, cur, reta);
  }

  cur.clear();

  for (int len = 1; len <= m; len++) {
    vector<cd> x(len);
    ld ang = 2 * PI / len;
    cd c(cos(ang), sin(ang));
    x[0] = 1;
    for (int i = 1; i < len; i++) {
      x[i] = x[i - 1] * c;
    }
    for (int i = 0; i <= m - len; i++) {
      x.push_back(0);
    }
    add(x);
  }

  {
    a.resize(m);
    for (int i = 0; i < m; i++) {
      a[i] = values[t[i] - 'a'];
    }
    conv_smart(a, cur, retb);
  }
  for (int len = 1; len <= n; len++) {
    place(s, len, norms_s);
    for (int i = 0; i < n - len + 1; i++) {
      cd l = lol[i + len - 1] - reta[(len - 1) * (n + 2) + i];

      assert(abs(real(l)) < eps);
      assert(abs(imag(l)) < eps);
    }
  }
  int len = min(n, m);
  while (!isok(len)) {
    if (verbose) {
      cout << "len = " << len << "\n";
    }
    len--;
  }
  cout << len << "\n";
  print(len);
  return 0;
}

Compilation message

necklace.cpp: In function 'int main()':
necklace.cpp:184:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  184 |     freopen ("___input___.txt", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 1740 KB Output is correct
2 Correct 11 ms 1736 KB Output is correct
3 Correct 9 ms 1776 KB Output is correct
4 Correct 14 ms 1364 KB Output is correct
5 Correct 12 ms 1748 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 1740 KB Output is correct
2 Correct 11 ms 1736 KB Output is correct
3 Correct 9 ms 1776 KB Output is correct
4 Correct 14 ms 1364 KB Output is correct
5 Correct 12 ms 1748 KB Output is correct
6 Correct 229 ms 23852 KB Output is correct
7 Correct 212 ms 23836 KB Output is correct
8 Correct 174 ms 19152 KB Output is correct
9 Correct 251 ms 23764 KB Output is correct
10 Correct 219 ms 23788 KB Output is correct
11 Correct 234 ms 23740 KB Output is correct
12 Correct 210 ms 23392 KB Output is correct

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 1740 KB Output is correct
2 Correct 11 ms 1736 KB Output is correct
3 Correct 9 ms 1776 KB Output is correct
4 Correct 14 ms 1364 KB Output is correct
5 Correct 12 ms 1748 KB Output is correct
6 Correct 229 ms 23852 KB Output is correct
7 Correct 212 ms 23836 KB Output is correct
8 Correct 174 ms 19152 KB Output is correct
9 Correct 251 ms 23764 KB Output is correct
10 Correct 219 ms 23788 KB Output is correct
11 Correct 234 ms 23740 KB Output is correct
12 Correct 210 ms 23392 KB Output is correct
13 Execution timed out 1628 ms 807712 KB Time limit exceeded
14 Halted 0 ms 0 KB -