Submission #656221

#TimeUsernameProblemLanguageResultExecution timeMemory
656221Do_you_copyNecklace (Subtask 1-3) (BOI19_necklace1)C++17
85 / 85
232 ms556 KiB
#include <bits/stdc++.h> //#define int long long #define fi first #define se second #define pb push_back #define faster ios_base::sync_with_stdio(0); cin.tie(0); using namespace std; using ll = long long; using ull = unsigned ll; using ld = long double; using pii = pair <int, int>; using pil = pair <int, ll>; using pli = pair <ll, int>; using pll = pair <ll, ll>; mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count()); ll min(const ll &a, const ll &b){ return (a < b) ? a : b; } ll max(const ll &a, const ll &b){ return (a > b) ? a : b; } //const ll Mod = 1000000007; //const ll Mod2 = 999999999989; //only use when required const int maxN = 1e5 + 1; int n, m; string rt; void kmp(const string &s, vector <int> &p){ int _n = s.length(); p.resize(_n); p[0] = -1; for (int i = 1, j = -1; i < _n; ++i){ while (j > -1 && s[j + 1] != s[i]){ j = p[j]; } if (s[j + 1] == s[i]) ++j; p[i] = j; } } tuple <int, int, int> get_ans(const string &s, const string &t, bool flag = 0){ tuple <int, int, int> ans = {0, 0, 0}; n = s.length(), m = t.length(); for (int i = 0; i < n; ++i){ vector <int> p1, p2; string s1 = s.substr(0, i); string s2 = s.substr(i, n - i); reverse(s1.begin(), s1.end()); kmp(s1 + "#" + t, p1); kmp(s2 + "#" + rt, p2); for (int j = 0; j < m; ++j){ ans = max(ans, {p1[i + j + 1] + p2[n + m - i - j - 1] + 2, i - p1[i + j + 1] - 1, flag ? m - j - 2 - p2[n + m - i - j - 1] : j - p1[i + j + 1]}); } } return ans; } void Init(){ string s, t; cin >> s >> t; rt = t; reverse(rt.begin(), rt.end()); tuple <int, int, int> ans = get_ans(s, t); swap(t, rt); ans = max(ans, get_ans(s, t, 1)); cout << get<0>(ans) << " " << get<1>(ans) << " " << get<2>(ans) << "\n"; } #define debu #define taskname "test" signed main(){ if (fopen(taskname".inp", "r")){ freopen(taskname".inp", "r", stdin); #ifdef debug freopen(taskname".out", "w", stdout); #endif } faster; ll tt = 1; //cin >> tt; while (tt--){ Init(); } if (fopen("timeout.txt", "r")){ ofstream timeout("timeout.txt"); timeout << 1000 * double(clock()) / CLOCKS_PER_SEC; #ifndef debug cerr << "\nTime elapsed: " << 1000 * double(clock()) / CLOCKS_PER_SEC << "ms\n"; #endif } }

Compilation message (stderr)

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