Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <cmath>
- #include <algorithm>
- #include <set>
- #include <map>
- #include <bitset>
- #include <string>
- #include <fstream>
- #include <vector>
- #include <cstring>
- #include <cassert>
- #include <ctime>
- #include <numeric>
- #include <unordered_map>
- #include <queue>
- using namespace std;
- typedef long long ll;
- typedef double ld;
- int solve();
- #define TASK "robots"
- #define err(...) fprintf(stdout, __VA_ARGS__), fflush(stdout)
- int main() {
- #ifdef HOME
- freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
- #else
- //freopen(TASK".in", "r", stdin), freopen(TASK".out", "w", stdout);
- #endif
- solve();
- }
- const ld pi = atan2(1, 1) * 4;
- const int LOG = 20;
- const int dd = (int)1e6 + (int)1e5;
- struct cmpl { ld real, imag; };
- cmpl operator + (cmpl const a, cmpl const b) { return{ a.real + b.real, a.imag + b.imag }; }
- cmpl operator - (cmpl const a, cmpl const b) { return{ a.real - b.real, a.imag - b.imag }; }
- cmpl operator * (cmpl const a, cmpl const b) { return{ a.real * b.real - a.imag * b.imag, a.real * b.imag + a.imag * b.real }; }
- cmpl operator / (cmpl const a, ld const b) { return{ a.real / b, a.imag / b }; }
- cmpl ang[LOG + 1][dd], A[dd], B[dd], C[dd];
- int rev[dd];
- void FFT(cmpl *A, bool inv) {
- int len = 1 << LOG;
- for (int i = 0; i < len; ++i)
- if (rev[i] < i)
- swap(A[i], A[rev[i]]);
- for (int k = 1; k <= LOG; ++k) {
- for (int l = 0; l < len; l += (1 << k)) {
- int L = 1 << (k - 1);
- for (int i = l; i < l + L; ++i) {
- cmpl t = A[i], cur = ang[k][i];
- if (inv)
- cur.imag = -cur.imag;
- A[i] = t + cur * A[i + L];
- A[i + L] = t - cur * A[i + L];
- }
- }
- }
- if (inv)
- for (int i = 0; i < len; ++i)
- A[i] = A[i] / len;
- }
- int solve() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- for (int k = 1; k <= LOG; ++k) {
- ld t = 2 * pi / (1 << k);
- cmpl cur = { 1, 0 };
- cmpl wn = { cos(t), sin(t) };
- for (int i = 0; i < dd; ++i) {
- ang[k][i] = cur;
- cur = cur * wn;
- }
- }
- for (int i = 0; i < (1 << LOG); ++i) {
- rev[i] = 0;
- for (int j = 0; j < LOG; ++j) if ((i >> j) & 1)
- rev[i] += 1 << (LOG - j - 1);
- }
- int n;
- string s, t;
- cin >> n;
- cin >> s >> t;
- const char* name = "ACGT";
- for (int i = 0; i < n; ++i)
- A[(i << 2) + strchr(name, s[i]) - name] = { 1, 0 };
- for (int i = 0; i < n; ++i)
- B[(i << 2) + strchr(name, t[i]) - name] = { 1, 0 };
- n <<= 2;
- reverse(B, B + n);
- for (int i = 0; i < n; ++i)
- A[i + n] = A[i];
- for (int i = 0; i < (n << 1); ++i)
- C[i] = { A[i].real, B[i].real };
- FFT(C, false);
- int N = 1 << LOG;
- for (int i = 1; i < N; ++i) {
- cmpl X = C[N - i];
- cmpl Y = { C[i].real, -C[i].imag };
- A[N - i] = (X + Y) / 2;
- B[N - i] = (X - Y) / 2;
- swap(B[N - i].real, B[N - i].imag);
- B[N - i].imag *= -1;
- }
- A[0] = { C[0].real, 0 };
- B[0] = { C[0].imag, 0 };
- for (int i = 0; i < (1 << LOG); ++i)
- A[i] = A[i] * B[i];
- FFT(A, true);
- int mx = 0, sd = 0;
- for (int i = 0; i < n; i += 4)
- if ((int)(A[i + n - 1].real + 0.5) > mx) {
- mx = (int)(A[i + n - 1].real + 0.5);
- sd = i >> 2;
- }
- cout << mx << " " << sd;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement