oj.uz

Submission #656123

# Submission time Handle Problem Language Result Execution time Memory
656123 2022-11-06T10:19:13 Z 600Mihnea Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 1500 ms 2528 KB 
bool home = 0;
bool verbose = 1;

#include <bits/stdc++.h>

using namespace std;

mt19937 rng(7777);

typedef long 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;
    }
  }
}

vector<cd> conv_smart(vector<cd> x, vector<cd> y) {
  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);
  vector<cd> sol;

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

  return sol;
}

ld values[26];

const ld eps = 1e-6;

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));
  vector<cd> cs(len);
  cs[0] = 1;
  for (int i = 1; i < len; i++) {
    cs[i] = cs[i - 1] * c;
  }
  vector<cd> a(n);
  for (int i = 0; i < n; i++) {
    a[i] = values[s[i] - 'a'];
  }
  vector<ld> sol(n - len + 1);
  vector<cd> lol = conv_smart(cs, a);
  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)) {
    len--;
  }
  cout << len << "\n";
  print(len);
  return 0;
}

Compilation message

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

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 9 ms 420 KB Output is correct
4 Correct 10 ms 340 KB Output is correct
5 Correct 18 ms 416 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 9 ms 420 KB Output is correct
4 Correct 10 ms 340 KB Output is correct
5 Correct 18 ms 416 KB Output is correct
6 Correct 55 ms 568 KB Output is correct
7 Correct 70 ms 596 KB Output is correct
8 Correct 219 ms 560 KB Output is correct
9 Correct 270 ms 556 KB Output is correct
10 Correct 310 ms 672 KB Output is correct
11 Correct 322 ms 640 KB Output is correct
12 Correct 271 ms 888 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 9 ms 420 KB Output is correct
4 Correct 10 ms 340 KB Output is correct
5 Correct 18 ms 416 KB Output is correct
6 Correct 55 ms 568 KB Output is correct
7 Correct 70 ms 596 KB Output is correct
8 Correct 219 ms 560 KB Output is correct
9 Correct 270 ms 556 KB Output is correct
10 Correct 310 ms 672 KB Output is correct
11 Correct 322 ms 640 KB Output is correct
12 Correct 271 ms 888 KB Output is correct
13 Execution timed out 1593 ms 2528 KB Time limit exceeded
14 Halted 0 ms 0 KB -