답안 #162377

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
162377 2019-11-07T20:07:43 Z Benq 원형 문자열 (IZhO13_rowords) C++14
32 / 100
212 ms 27000 KB
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;
 
typedef double db;
typedef long long ll;
typedef long double ld;
typedef string str;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef complex<ld> cd;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef vector<str> vs;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); i--)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a : x)

#define mp make_pair
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define rsz resize
#define ins insert

const int MOD = 1e9+7; // 998244353 = (119<<23)+1
const ll INF = 1e18;
const int MX = 2e5+5;
const ld PI = 4*atan((ld)1);

template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>

using namespace __gnu_pbds;
using namespace __gnu_cxx;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define ook order_of_key
#define fbo find_by_order

namespace input {
    template<class T> void re(complex<T>& x);
    template<class T1, class T2> void re(pair<T1,T2>& p);
    template<class T> void re(vector<T>& a);
    template<class T, size_t SZ> void re(array<T,SZ>& a);

    template<class T> void re(T& x) { cin >> x; }
    void re(double& x) { string t; re(t); x = stod(t); }
    void re(ld& x) { string t; re(t); x = stold(t); }
    template<class T, class... Ts> void re(T& t, Ts&... ts) { 
        re(t); re(ts...); 
    }

    template<class T> void re(complex<T>& x) { T a,b; re(a,b); x = cd(a,b); }
    template<class T1, class T2> void re(pair<T1,T2>& p) { re(p.f,p.s); }
    template<class T> void re(vector<T>& a) { F0R(i,sz(a)) re(a[i]); }
    template<class T, size_t SZ> void re(array<T,SZ>& a) { F0R(i,SZ) re(a[i]); }
}

using namespace input;

namespace output {
    void pr(int x) { cout << x; }
    void pr(long x) { cout << x; }
    void pr(ll x) { cout << x; }
    void pr(unsigned x) { cout << x; }
    void pr(unsigned long x) { cout << x; }
    void pr(unsigned long long x) { cout << x; }
    void pr(float x) { cout << x; }
    void pr(double x) { cout << x; }
    void pr(ld x) { cout << x; }
    void pr(char x) { cout << x; }
    void pr(const char* x) { cout << x; }
    void pr(const string& x) { cout << x; }
    void pr(bool x) { pr(x ? "true" : "false"); }
    template<class T> void pr(const complex<T>& x) { cout << x; }
    
    template<class T1, class T2> void pr(const pair<T1,T2>& x);
    template<class T> void pr(const T& x);
    
    template<class T, class... Ts> void pr(const T& t, const Ts&... ts) { 
        pr(t); pr(ts...); 
    }
    template<class T1, class T2> void pr(const pair<T1,T2>& x) { 
        pr("{",x.f,", ",x.s,"}"); 
    }
    template<class T> void pr(const T& x) { 
        pr("{"); // const iterator needed for vector<bool>
        bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; 
        pr("}");
    }
    
    void ps() { pr("\n"); } // print w/ spaces
    template<class T, class... Ts> void ps(const T& t, const Ts&... ts) { 
        pr(t); if (sizeof...(ts)) pr(" "); ps(ts...); 
    }
    
    void pc() { pr("]\n"); } // debug w/ commas
    template<class T, class... Ts> void pc(const T& t, const Ts&... ts) { 
        pr(t); if (sizeof...(ts)) pr(", "); pc(ts...); 
    }
    #define dbg(x...) pr("[",#x,"] = ["), pc(x);
}

using namespace output;

namespace io {
    void setIn(string s) { freopen(s.c_str(),"r",stdin); }
    void setOut(string s) { freopen(s.c_str(),"w",stdout); }
    void setIO(string s = "") {
        cin.sync_with_stdio(0); cin.tie(0); // fast I/O
        cin.exceptions(cin.failbit); // ex. throws exception when you try to read letter into int
        if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
    }
}

using namespace io;

template<class T> T invGeneral(T a, T b) {
	a %= b; if (a == 0) return b == 1 ? 0 : -1;
	T x = invGeneral(b,a); 
	return x == -1 ? -1 : ((1-(ll)b*x)/a+b)%b;
}

template<class T> struct modular {
	T val; 
	explicit operator T() const { return val; }
	modular() { val = 0; }
	modular(const ll& v) { 
		val = (-MOD <= v && v <= MOD) ? v : v % MOD;
		if (val < 0) val += MOD;
	}
	
	// friend ostream& operator<<(ostream& os, const modular& a) { return os << a.val; }
	friend void pr(const modular& a) { pr(a.val); }
	friend void re(modular& a) { ll x; re(x); a = modular(x); }
   
	friend bool operator==(const modular& a, const modular& b) { return a.val == b.val; }
	friend bool operator!=(const modular& a, const modular& b) { return !(a == b); }
	friend bool operator<(const modular& a, const modular& b) { return a.val < b.val; }

	modular operator-() const { return modular(-val); }
	modular& operator+=(const modular& m) { if ((val += m.val) >= MOD) val -= MOD; return *this; }
	modular& operator-=(const modular& m) { if ((val -= m.val) < 0) val += MOD; return *this; }
	modular& operator*=(const modular& m) { val = (ll)val*m.val%MOD; return *this; }
	friend modular pow(modular a, ll p) {
		modular ans = 1; for (; p; p /= 2, a *= a) if (p&1) ans *= a;
		return ans;
	}
	friend modular inv(const modular& a) { 
		auto i = invGeneral(a.val,MOD); assert(i != -1);
		return i;
	} // equivalent to return exp(b,MOD-2) if MOD is prime
	modular& operator/=(const modular& m) { return (*this) *= inv(m); }
	
	friend modular operator+(modular a, const modular& b) { return a += b; }
	friend modular operator-(modular a, const modular& b) { return a -= b; }
	friend modular operator*(modular a, const modular& b) { return a *= b; }
	
	friend modular operator/(modular a, const modular& b) { return a /= b; }
};

typedef modular<int> mi;
typedef pair<mi,mi> pmi;
typedef vector<mi> vmi;
typedef vector<pmi> vpmi;

pi dp[2001][4001];
str A,B;
 
void init() {
    FOR(i,1,sz(A)+1) FOR(j,1,sz(B)+1) { // naive LCS, store where value came from
        pi& bes = dp[i][j]; bes = {-1,-1};
        ckmax(bes,{dp[i-1][j].f,0});
        ckmax(bes,{dp[i-1][j-1].f+(A[i-1] == B[j-1]),-1});
        ckmax(bes,{dp[i][j-1].f,-2});
        bes.s *= -1;
    }
}
void adjust(int col) { // remove col'th character of b, adjust DP
    int x = 1;
    while (x <= sz(A) && dp[x][col].s == 0) x ++;
    if (x > sz(A)) return; // no adjustments to dp
    pi cur = {x,col}; 
    while (cur.f <= sz(A) && cur.s <= sz(B)) {
        dp[cur.f][cur.s].s = 0;
        if (cur.s < sz(B) && dp[cur.f][cur.s+1].s == 2) {
            cur.s ++;
        } else if (cur.f < sz(A) && cur.s < sz(B) 
        	&& dp[cur.f+1][cur.s+1].s == 1) {
            cur.f ++, cur.s ++;
        } else cur.f ++;
    }
}
int getAns(pi x) {
    int lo = x.s-sz(B)/2, ret = 0;
    while (x.f && x.s > lo) {
        if (dp[x.f][x.s].s == 0) x.f --;
        else if (dp[x.f][x.s].s == 1) ret ++, x.f --, x.s --;
        else x.s --;
    }
    return ret;
}
int circLCS(str a, str b) {
    A = a, B = b+b; init();
    int ans = 0;
    F0R(i,sz(b)) {
        ans = max(ans,getAns({sz(a),i+sz(b)}));
        adjust(i+1);
    }
    return ans;
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    str a,b; cin >> a >> b;
    int ans = circLCS(a,b);
    reverse(all(a));
    ckmax(ans,circLCS(a,b));
    cout << ans;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?), set tle
	* do smth instead of nothing and stay organized
*/

Compilation message

rowords.cpp: In function 'void io::setIn(std::__cxx11::string)':
rowords.cpp:135:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
rowords.cpp: In function 'void io::setOut(std::__cxx11::string)':
rowords.cpp:136:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 632 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 13 ms 6008 KB Output is correct
7 Correct 55 ms 20084 KB Output is correct
8 Incorrect 167 ms 20084 KB Output isn't correct
9 Incorrect 173 ms 20088 KB Output isn't correct
10 Incorrect 155 ms 20212 KB Output isn't correct
11 Incorrect 162 ms 22048 KB Output isn't correct
12 Correct 82 ms 25336 KB Output is correct
13 Incorrect 212 ms 25208 KB Output isn't correct
14 Incorrect 177 ms 23036 KB Output isn't correct
15 Incorrect 212 ms 26820 KB Output isn't correct
16 Incorrect 189 ms 22236 KB Output isn't correct
17 Incorrect 128 ms 19232 KB Output isn't correct
18 Incorrect 203 ms 27000 KB Output isn't correct
19 Incorrect 139 ms 20088 KB Output isn't correct
20 Incorrect 199 ms 24056 KB Output isn't correct
21 Incorrect 33 ms 11256 KB Output isn't correct
22 Incorrect 64 ms 14712 KB Output isn't correct
23 Incorrect 89 ms 17656 KB Output isn't correct
24 Incorrect 102 ms 18424 KB Output isn't correct
25 Incorrect 142 ms 22520 KB Output isn't correct