oj.uz

답안 #656139

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
656139 2022-11-06T10:39:41 Z 600Mihnea Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 1500 ms 1492 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>;
const int N = 1 << 13;


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) {
  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;

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) {
  place(s, len, norms_s);
  place(t, len, norms_t);
  int n = (int) norms_s.size();
  int m = (int) norms_t.size();
  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) {
  place(s, len, norms_s);
  place(t, len, norms_t);
  int n = (int) norms_s.size();
  int m = (int) norms_t.size();
  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);
      }
    }
  }
}

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();
  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:161:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |     freopen ("___input___.txt", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 852 KB Output is correct
2 Correct 41 ms 852 KB Output is correct
3 Correct 187 ms 852 KB Output is correct
4 Correct 305 ms 820 KB Output is correct
5 Correct 337 ms 864 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 852 KB Output is correct
2 Correct 41 ms 852 KB Output is correct
3 Correct 187 ms 852 KB Output is correct
4 Correct 305 ms 820 KB Output is correct
5 Correct 337 ms 864 KB Output is correct
6 Correct 195 ms 852 KB Output is correct
7 Correct 298 ms 852 KB Output is correct
8 Correct 825 ms 852 KB Output is correct
9 Correct 1137 ms 852 KB Output is correct
10 Correct 1215 ms 852 KB Output is correct
11 Correct 1302 ms 852 KB Output is correct
12 Correct 1020 ms 852 KB Output is correct

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 852 KB Output is correct
2 Correct 41 ms 852 KB Output is correct
3 Correct 187 ms 852 KB Output is correct
4 Correct 305 ms 820 KB Output is correct
5 Correct 337 ms 864 KB Output is correct
6 Correct 195 ms 852 KB Output is correct
7 Correct 298 ms 852 KB Output is correct
8 Correct 825 ms 852 KB Output is correct
9 Correct 1137 ms 852 KB Output is correct
10 Correct 1215 ms 852 KB Output is correct
11 Correct 1302 ms 852 KB Output is correct
12 Correct 1020 ms 852 KB Output is correct
13 Execution timed out 1567 ms 1492 KB Time limit exceeded
14 Halted 0 ms 0 KB -