제출 #658233

#제출 시각아이디문제언어결과실행 시간메모리
658233600MihneaNecklace (Subtask 1-3) (BOI19_necklace1)C++17
45 / 85
1588 ms807876 KiB
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; 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) { int n = 1; while (n <= (int)a.size() + (int)b.size()) n *= 2; 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; vector<cd> reta, retb; 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) { if (len > (int) s.size() || len > (int) t.size()) { return 0; } int n = (int) s.size() - len + 1; int m = (int) t.size() - len + 1; norms_s.resize(n); norms_t.resize(m); for (int i = 0; i < n; i++) { norms_s[i] = norm(reta[(len - 1) * ((int) s.size() + 2) + i]); } for (int i = 0; i < m; i++) { norms_t[i] = norm(retb[(len - 1) * ((int) t.size() + 2) + i]); } 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) { int n = (int) s.size() - len + 1; int m = (int) t.size() - len + 1; norms_s.resize(n); norms_t.resize(m); for (int i = 0; i < n; i++) { norms_s[i] = norm(reta[(len - 1) * ((int) s.size() + 2) + i]); } for (int i = 0; i < m; i++) { norms_t[i] = norm(retb[(len - 1) * ((int) t.size() + 2) + i]); } 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); } } } } vector<cd> cur; void add(vector<cd> &v) { for (auto &x : v) { cur.push_back(x); } } 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(); for (int len = 1; len <= n; len++) { vector<cd> x(len); ld ang = 2 * PI / len; cd c(cos(ang), sin(ang)); x[0] = 1; for (int i = 1; i < len; i++) { x[i] = x[i - 1] * c; } for (int i = 0; i <= n - len; i++) { x.push_back(0); } add(x); } { a.resize(n); for (int i = 0; i < n; i++) { a[i] = values[s[i] - 'a']; } conv_smart(a, cur, reta); } cur.clear(); for (int len = 1; len <= m; len++) { vector<cd> x(len); ld ang = 2 * PI / len; cd c(cos(ang), sin(ang)); x[0] = 1; for (int i = 1; i < len; i++) { x[i] = x[i - 1] * c; } for (int i = 0; i <= m - len; i++) { x.push_back(0); } add(x); } { a.resize(m); for (int i = 0; i < m; i++) { a[i] = values[t[i] - 'a']; } conv_smart(a, cur, retb); } for (int len = 1; len <= n; len++) { place(s, len, norms_s); for (int i = 0; i < n - len + 1; i++) { cd l = lol[i + len - 1] - reta[(len - 1) * (n + 2) + i]; assert(abs(real(l)) < eps); assert(abs(imag(l)) < eps); } } int len = min(n, m); while (!isok(len)) { if (verbose) { cout << "len = " << len << "\n"; } len--; } cout << len << "\n"; print(len); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

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