oj.uz

답안 #658233

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
658233 2022-11-12T13:15:53 Z 600Mihnea Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 1500 ms 807876 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 1736 KB Output is correct
2 Correct 11 ms 1856 KB Output is correct
3 Correct 8 ms 1776 KB Output is correct
4 Correct 10 ms 1364 KB Output is correct
5 Correct 11 ms 1812 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 1736 KB Output is correct
2 Correct 11 ms 1856 KB Output is correct
3 Correct 8 ms 1776 KB Output is correct
4 Correct 10 ms 1364 KB Output is correct
5 Correct 11 ms 1812 KB Output is correct
6 Correct 220 ms 23860 KB Output is correct
7 Correct 222 ms 23840 KB Output is correct
8 Correct 176 ms 19164 KB Output is correct
9 Correct 209 ms 23828 KB Output is correct
10 Correct 216 ms 23684 KB Output is correct
11 Correct 221 ms 23680 KB Output is correct
12 Correct 208 ms 23404 KB Output is correct

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 1736 KB Output is correct
2 Correct 11 ms 1856 KB Output is correct
3 Correct 8 ms 1776 KB Output is correct
4 Correct 10 ms 1364 KB Output is correct
5 Correct 11 ms 1812 KB Output is correct
6 Correct 220 ms 23860 KB Output is correct
7 Correct 222 ms 23840 KB Output is correct
8 Correct 176 ms 19164 KB Output is correct
9 Correct 209 ms 23828 KB Output is correct
10 Correct 216 ms 23684 KB Output is correct
11 Correct 221 ms 23680 KB Output is correct
12 Correct 208 ms 23404 KB Output is correct
13 Execution timed out 1588 ms 807876 KB Time limit exceeded
14 Halted 0 ms 0 KB -