Advertisement
Guest User

Untitled

a guest
Mar 2nd, 2017
224
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
PL/I 3.22 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #include <cmath>
  6. #include <algorithm>
  7. #include <set>
  8. #include <map>
  9. #include <bitset>
  10. #include <string>
  11. #include <fstream>
  12. #include <vector>
  13. #include <cstring>
  14. #include <cassert>
  15. #include <ctime>
  16. #include <numeric>
  17. #include <unordered_map>
  18. #include <queue>
  19.  
  20. using namespace std;
  21.  
  22. typedef long long ll;
  23. typedef double ld;
  24.  
  25. int solve();
  26. #define TASK "robots"
  27. #define err(...) fprintf(stdout, __VA_ARGS__), fflush(stdout)
  28.  
  29. int main() {
  30. #ifdef HOME
  31.     freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  32. #else
  33.     //freopen(TASK".in", "r", stdin), freopen(TASK".out", "w", stdout);
  34. #endif
  35.     solve();
  36. }
  37.  
  38. const ld pi = atan2(1, 1) * 4;
  39. const int LOG = 20;
  40. const int dd = (int)1e6 + (int)1e5;
  41.  
  42. struct cmpl { ld real, imag; };
  43. cmpl operator + (cmpl const a, cmpl const b) { return{ a.real + b.real, a.imag + b.imag }; }
  44. cmpl operator - (cmpl const a, cmpl const b) { return{ a.real - b.real, a.imag - b.imag }; }
  45. 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 }; }
  46. cmpl operator / (cmpl const a, ld const b) { return{ a.real / b, a.imag / b }; }
  47.  
  48. cmpl ang[LOG + 1][dd], A[dd], B[dd], C[dd];
  49. int rev[dd];
  50.  
  51. void FFT(cmpl *A, bool inv) {
  52.     int len = 1 << LOG;
  53.  
  54.     for (int i = 0; i < len; ++i)
  55.         if (rev[i] < i)
  56.             swap(A[i], A[rev[i]]);
  57.  
  58.     for (int k = 1; k <= LOG; ++k) {
  59.         for (int l = 0; l < len; l += (1 << k)) {
  60.  
  61.             int L = 1 << (k - 1);
  62.  
  63.             for (int i = l; i < l + L; ++i) {
  64.  
  65.                 cmpl t = A[i], cur = ang[k][i];
  66.                 if (inv)
  67.                     cur.imag = -cur.imag;
  68.                 A[i] = t + cur * A[i + L];
  69.                 A[i + L] = t - cur * A[i + L];
  70.             }
  71.  
  72.         }
  73.     }
  74.     if (inv)
  75.         for (int i = 0; i < len; ++i)
  76.             A[i] = A[i] / len;
  77. }
  78.  
  79. int solve() {
  80.     ios_base::sync_with_stdio(0);
  81.     cin.tie(0);
  82.  
  83.     for (int k = 1; k <= LOG; ++k) {
  84.         ld t = 2 * pi / (1 << k);
  85.         cmpl cur = { 1, 0 };
  86.         cmpl wn = { cos(t), sin(t) };
  87.         for (int i = 0; i < dd; ++i) {
  88.             ang[k][i] = cur;
  89.             cur = cur * wn;
  90.         }
  91.     }
  92.  
  93.     for (int i = 0; i < (1 << LOG); ++i) {
  94.         rev[i] = 0;
  95.         for (int j = 0; j < LOG; ++j) if ((i >> j) & 1)
  96.             rev[i] += 1 << (LOG - j - 1);
  97.     }
  98.  
  99.     int n;
  100.     string s, t;
  101.     cin >> n;
  102.     cin >> s >> t;
  103.  
  104.     const char* name = "ACGT";
  105.  
  106.     for (int i = 0; i < n; ++i)
  107.         A[(i << 2) + strchr(name, s[i]) - name] = { 1, 0 };
  108.  
  109.     for (int i = 0; i < n; ++i)
  110.         B[(i << 2) + strchr(name, t[i]) - name] = { 1, 0 };
  111.  
  112.     n <<= 2;
  113.  
  114.     reverse(B, B + n);
  115.  
  116.     for (int i = 0; i < n; ++i)
  117.         A[i + n] = A[i];
  118.  
  119.    
  120.     for (int i = 0; i < (n << 1); ++i)
  121.         C[i] = { A[i].real, B[i].real };
  122.    
  123.  
  124.     FFT(C, false);
  125.  
  126.     int N = 1 << LOG;
  127.  
  128.     for (int i = 1; i < N; ++i) {
  129.         cmpl X = C[N - i];
  130.         cmpl Y = { C[i].real, -C[i].imag };
  131.  
  132.         A[N - i] = (X + Y) / 2;
  133.         B[N - i] = (X - Y) / 2;
  134.         swap(B[N - i].real, B[N - i].imag);
  135.         B[N - i].imag *= -1;
  136.     }
  137.  
  138.     A[0] = { C[0].real, 0 };
  139.     B[0] = { C[0].imag, 0 };
  140.  
  141.     for (int i = 0; i < (1 << LOG); ++i)
  142.         A[i] = A[i] * B[i];
  143.  
  144.     FFT(A, true);
  145.  
  146.     int mx = 0, sd = 0;
  147.  
  148.     for (int i = 0; i < n; i += 4)
  149.         if ((int)(A[i + n - 1].real + 0.5) > mx) {
  150.             mx = (int)(A[i + n - 1].real + 0.5);
  151.             sd = i >> 2;
  152.         }
  153.     cout << mx << " " << sd;
  154.     return 0;
  155. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement