Submission #656161

#TimeUsernameProblemLanguageResultExecution timeMemory
656161600MihneaNecklace (Subtask 1-3) (BOI19_necklace1)C++17
45 / 85
1591 ms70988 KiB
bool home = 0; bool verbose = 1; #include <bits/stdc++.h> using namespace std; int comps = 0; void compute(vector<vector<int>>& dp, string &s, string &t) { int n = (int) s.size(); int m = (int) t.size(); assert((int) dp.size() == n); for (int i = 0; i < n; i++) { assert((int) dp[i].size() == m); } for (int i = n - 1; i >= 0; i--) { for (int j = m - 1; j >= 0; j--) { if (s[i] == t[j]) { dp[i][j] = 1; if (i + 1 < n && j + 1 < m) { dp[i][j] += dp[i + 1][j + 1]; } } else { dp[i][j] = 0; } } } } vector<vector<int>> longst; vector<vector<int>> longts; string s; string t; int get_longest(int last, int first, bool cs) { if (cs == 0) { if (!(0 <= last && last < (int) s.size() && 0 <= first && first < (int) t.size())) { return 0; } int max_possible_len = min(last + 1, (int) t.size() - first); for (int len = max_possible_len; len >= 1; len--) { if (longst[last - len + 1][first] >= len) { return len; } } return 0; } else { if (!(0 <= last && last < (int) t.size() && 0 <= first && first < (int) s.size())) { return 0; } int max_possible_len = min(last + 1, (int) s.size() - first); for (int len = max_possible_len; len >= 1; len--) { if (longts[last - len + 1][first] >= len) { return len; } } return 0; } } int main() { 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 sol = -1, l, f, r; for (int rev_t = 0; rev_t <= 1; rev_t++) { int n = (int) s.size(), m = (int) t.size(); longst.clear(); longts.clear(); longst.resize(n, vector<int> (m)); longts.resize(m, vector<int> (n)); compute(longst, s, t); compute(longts, t, s); /** AB BA **/ for (int last_a = 0; last_a < n; last_a++) { for (int first_a = 0; first_a < m; first_a++) { int first_b = last_a + 1; int last_b = first_a - 1; int cur = get_longest(last_a, first_a, 0) + get_longest(last_b, first_b, 1); if (cur > sol) { sol = cur; l = last_a; f = first_a; r = rev_t; } } } reverse(t.begin(), t.end()); } if (r) { reverse(t.begin(), t.end()); } int n = (int) s.size(), m = (int) t.size(); longst.clear(); longts.clear(); longst.resize(n, vector<int> (m)); longts.resize(m, vector<int> (n)); compute(longst, s, t); compute(longts, t, s); int rev = r; int last_a = l; int first_a = f; int first_b = last_a + 1; int last_b = first_a - 1; int len_a = get_longest(last_a, first_a, 0); int len_b = get_longest(last_b, first_b, 1); /// [last_a - len_a] /// [last_b - len_b] int jump_a = last_a - len_a + 1; int jump_b; /// [a, b] /// [b, a] if (rev == 0) { jump_b = last_b - len_b + 1; } else { jump_b = (int) t.size() - (first_a + len_a); } if (verbose) { cout << "\t\t\t\t\tcomps = " << comps << "\n"; } cout << sol << "\n"; cout << jump_a << " " << jump_b << "\n"; return 0; }

Compilation message (stderr)

necklace.cpp: In function 'int main()':
necklace.cpp:73:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     freopen ("___input___.txt", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
necklace.cpp:138:3: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  138 |   if (rev == 0) {
      |   ^~
necklace.cpp:141:40: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
  141 |     jump_b = (int) t.size() - (first_a + len_a);
      |                               ~~~~~~~~~^~~~~~~~
necklace.cpp:132:23: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
  132 |   int jump_a = last_a - len_a + 1;
      |                ~~~~~~~^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...