Submission #874320

#TimeUsernameProblemLanguageResultExecution timeMemory
874320RedGrey1993Round words (IZhO13_rowords)C++17
100 / 100
76 ms22124 KiB
#include <bits/stdc++.h> using namespace std; template <typename T1, typename T2> istream &operator>>(istream &is, const pair<T1, T2> &pa) { is >> pa.first >> pa.second; return is; } template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; } template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa) { os << "(" << pa.first << "," << pa.second << ")"; return os; } template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; } template <typename T> ostream &operator<<(ostream &os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; } template <typename T> ostream &operator<<(ostream &os, const set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template <typename T> ostream &operator<<(ostream &os, const multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template <typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; } template <typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; } template <typename T> void resize_array(vector<T> &vec, int len) { vec.resize(len); } template <typename T, typename... Args> void resize_array(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) resize_array(v, args...); } template <typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); } template <typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); } long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; } mt19937 mrand(random_device{}()); int rnd(int x) { return mrand() % x; } template <unsigned int MOD> class ModInt { public: ModInt(unsigned long long _v = 0) { set_v((_v % MOD + MOD)); } explicit operator bool() const { return val != 0; } ModInt operator-() const { return ModInt() - *this; } ModInt operator+(const ModInt &r) const { return ModInt().set_v(val + r.val); } ModInt operator-(const ModInt &r) const { return ModInt().set_v(val + MOD - r.val); } ModInt operator*(const ModInt &r) const { return ModInt().set_v((unsigned int)((unsigned long long)(val)*r.val % MOD)); } ModInt operator/(const ModInt &r) const { return *this * r.inv(); } ModInt &operator+=(const ModInt &r) { return *this = *this + r; } ModInt &operator-=(const ModInt &r) { return *this = *this - r; } ModInt &operator*=(const ModInt &r) { return *this = *this * r; } ModInt &operator/=(const ModInt &r) { return *this = *this / r; } // ModInt &operator=(unsigned long long _v) { set_v((_v % MOD + MOD)); return *this; } unsigned int operator=(unsigned long long _v) { set_v((_v % MOD + MOD)); return val; } bool operator==(const ModInt &r) const { return val == r.val; } bool operator!=(const ModInt &r) const { return val != r.val; } ModInt pow(long long n) const { ModInt x = *this, r = 1; while (n) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; } ModInt inv() const { return pow(MOD - 2); } unsigned int get_val() { return val; } friend ostream &operator<<(ostream &os, const ModInt &r) { return os << r.val; } friend istream &operator>>(istream &is, ModInt &r) { return is >> r.val; } private: unsigned int val; ModInt &set_v(unsigned int _v) { val = (_v < MOD) ? _v : _v - MOD; return *this; } }; constexpr unsigned int mod = 1e9+7; using Mint = ModInt<mod>; #define rep(i, a, n) for (int i = a; i < (n); i++) #define per(i, a, n) for (int i = (n)-1; i >= a; i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(), (x).end() #define fi first #define se second #define sz(x) ((int)(x).size()) typedef vector<int> vi; typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; typedef pair<int, int> pii; typedef double db; #if DEBUG #define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl; #else #define dbg(x) #endif using Mint2 = ModInt<mod-1>; class Solution { struct Line { long long m, c; long long Eval(long long x) { return m * x + c; } long double IntersectX(Line l) { return (long double)(c - l.c) / (l.m - m); } }; public: void Solve() { string s,t; while(cin>>s>>t) { s += s; // dbg(s); int n = sz(s), m=sz(t); auto clcs = [&] () { vector<vi> dp(n+1, vi(m+1)); vector<vi> parent(n+1, vi(m+1)); rep(i,1,n+1) parent[i][0] = 2; rep(i,0,n) { rep(j,0,m) { if (s[i] == t[j]) dp[i+1][j+1] = dp[i][j] + 1; else dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]); if (dp[i+1][j+1] == dp[i+1][j]) parent[i+1][j+1] = 0; else if (s[i] == t[j] && dp[i+1][j+1] == dp[i][j] + 1) parent[i+1][j+1] = 1; else parent[i+1][j+1] = 2; } } auto lcs = [&] (int root) { int x = root + n/2; int y = m; int cnt = 0; while (x > root && y > 0) { if (parent[x][y] == 1) { cnt++; x--; y--; // dbg(mp(x,y)); // dbg(cnt); } else if (parent[x][y] == 0) y--; else x--; } return cnt; }; auto reroot = [&] (int root) { int x = root; int y = 0; while (y <= m && parent[x][y] != 1) y++; if (y > m) return; parent[x][y] = 0; while (x < n && y < m) { if (parent[x+1][y] == 2) { x++; parent[x][y] = 0; } else if (parent[x+1][y+1] == 1) { x++; y++; parent[x][y] = 0; } else { y++; } } while (x < n && parent[x+1][y] == 2) { x++; parent[x][y] = 0; } }; int ans = 0; ans = max(ans, lcs(0)); rep(root, 1, n/2) { reroot(root); ans = max(ans, lcs(root)); } // dbg(ans); return ans; }; int ans = clcs(); reverse(all(s)); ans = max(ans, clcs()); cout << ans << endl; } } private: }; // #define USACO 1 void set_io(const string &name = "") { ios::sync_with_stdio(false); cin.tie(nullptr); #if FILE_IO || USACO if (!name.empty()) { freopen((name + ".in").c_str(), "r", stdin); freopen((name + ".out").c_str(), "w", stdout); } #endif } int main() { #if USACO set_io("time"); #else set_io("input"); #endif Solution().Solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...