oj.uz

답안 #656134

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
656134 2022-11-06T10:32:55 Z 600Mihnea Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 1500 ms 1524 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;
  assert(x >= 2);
  assert(x % 2 == 0);
  return 1 + getlog2(x / 2);
}

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

  assert((1 << k) == 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> x, vector<cd> y, vector<cd> &sol) {
  int n = 1;
  while (n <= (int)x.size() + (int)y.size()) n *= 2;

  x.resize(n, 0);
  y.resize(n, 0);

  vector<cd> a(x.begin(), x.end());
  vector<cd> b(y.begin(), y.end());

  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<ld> place(string s, int len) {
  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'];
  }
  vector<ld> sol(n - len + 1);
  conv_smart(cs, a, lol);
  for (int i = 0; i < n - len + 1; i++) {
    sol[i] = norm(lol[i + len - 1]);
  }
  return sol;
}

string s, t;


bool isok(int len) {
  vector<ld> norms_s = place(s, len);
  vector<ld> norms_t = place(t, len);
  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) {
  vector<ld> norms_s = place(s, len);
  vector<ld> norms_t = place(t, len);
  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)) {
    ///cout << "len = " << len << "\n";
    len--;
  }
  cout << len << "\n";
  print(len);
  return 0;
}

Compilation message

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

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Correct 5 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 18 ms 440 KB Output is correct
7 Correct 24 ms 456 KB Output is correct
8 Correct 74 ms 468 KB Output is correct
9 Correct 90 ms 460 KB Output is correct
10 Correct 167 ms 480 KB Output is correct
11 Correct 107 ms 444 KB Output is correct
12 Correct 93 ms 456 KB Output is correct

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 18 ms 440 KB Output is correct
7 Correct 24 ms 456 KB Output is correct
8 Correct 74 ms 468 KB Output is correct
9 Correct 90 ms 460 KB Output is correct
10 Correct 167 ms 480 KB Output is correct
11 Correct 107 ms 444 KB Output is correct
12 Correct 93 ms 456 KB Output is correct
13 Execution timed out 1583 ms 1524 KB Time limit exceeded
14 Halted 0 ms 0 KB -