oj.uz

답안 #933659

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
933659 2024-02-26T04:15:37 Z mgch 원형 문자열 (IZhO13_rowords) C++14
72 / 100
 2000 ms 5724 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
/** so there is complicated algo based on some research let's get it later
 * 
 * 
 *  you have to get that |lcs(a, b) - lcs(a, b[1..n-1] + b[0])| <= 2
 *  so if you have ans >= lcs(a, b) + 2 then ... push it
 * */
 
const int N = 2024;
 
int dp[N][N], n, m;
string s[N], t[N];
 
int lcs(const string &a, const string &b) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
            if (a[i] == b[j]) {
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1);
            }
        }
    }
    return dp[n][m];
}

namespace LCS0SPOJ { //thx sk1
    struct TBitset {
    	int sz, n;
    	unsigned a[N / 32 + 3];
    	TBitset() { n = 0; }
    	TBitset(int _n) {
    		memset(a, 0, sizeof(a));
    		sz = _n / 32 + 2; n = _n;
    	}
    	void Set(int x, int v) {
    		if(v == 1) {
    			a[x >> 5] |= 1U << (x & 31);
    		} else {
    			if((a[x >> 5] >> (x & 31)) & 1)
    				a[x >> 5] ^= 1U << (x & 31);
    		}
    	}
    	int Get(int x) {
    		return (a[x >> 5] >> (x & 31)) & 1;
    	}
    	TBitset operator | (const TBitset & b) {
    		TBitset r(n);
    		for(int i = 0; i < sz; ++i)
    			r.a[i] = a[i] | b.a[i];
    		return r;
    	}
    	TBitset operator & (const TBitset & b) {
    		TBitset r(n);
    		for(int i = 0; i < sz; ++i)
    			r.a[i] = a[i] & b.a[i];
    		return r;
    	}
    	TBitset operator ^ (const TBitset & b) {
    		TBitset r(n);
    		for(int i = 0; i < sz; ++i)
    			r.a[i] = a[i] ^ b.a[i];
    		return r;
    	}
    	void operator |= (const TBitset & b) {
    		for(int i = 0; i < sz; ++i)
    			a[i] |= b.a[i];
    	}
    	void operator &= (const TBitset & b) {
    		for(int i = 0; i < sz; ++i)
    			a[i] &= b.a[i];
    	}
    	void operator ^= (const TBitset & b) {
    		for(int i = 0; i < sz; ++i)
    			a[i] ^= b.a[i];
    	}
    	TBitset operator + (const TBitset & b) {
    		TBitset r(n);
    		bool ok = false;
    		for(int i = 0; i + 1 < sz; ++i) {
    			long long sum = (long long)a[i] + (long long)b.a[i] + ok;
    			r.a[i] = sum & ((1LL << 32) - 1);
    			ok = sum >> 32;
    		}
    		return r;
    	}
    	void operator += (const TBitset & b) {
    		memset(a, 0, sizeof(a));
    		for(int i = 0; i < sz; ++i) {
    			long long sum = (long long)a[i] + (long long)b.a[i];
    			a[i] += sum & ((1LL << 32) - 1);
    			a[i + 1] += sum >> 32;
    		}
    	}
    	TBitset operator ~ () {
    		TBitset r(n);
    		for(int i = 0; i < sz; ++i) {
    			r.a[i] = ~a[i];
    		}
    		return r;
    	}
    	void reset() {
    		memset(a, 0, sizeof(a));
    	}
    } b, nb, nxb, eq[26], neq[26];
    
    int lcs(const string &s, const string &t) {
        int n = (int)s.length();
        int m = (int)t.length();
        b = TBitset(m + 1); nb = TBitset(m + 1);
    	for(int i = 0; i < 26; ++i) {
    		eq[i] = TBitset(m + 1);
    		neq[i] = TBitset(m + 1);
    	}
    	for(int i = 0; i < 26; ++i)
    		for(int j = 0; j < m; ++j) {
    			neq[i].Set(j, 1);
    			eq[i].Set(j, 0);
    		}
    	for(int i = 0; i < m; ++i) {
    		eq[t[i] - 'a'].Set(i, 1);
    		neq[t[i] - 'a'].Set(i, 0);
    		nb.Set(i, 1);
    	}
    	int ans = 0;
    	for(int i = 0; i < n; ++i) {
    		int dig = s[i] - 'a';
    		nxb = (nb + (nb & eq[dig])) | (nb & neq[dig]);
    		if(nxb.Get(m))
    			++ans;
    		for(int i = m; i < m + 32; ++i)
    			nxb.Set(m, 0);
    		nb = nxb;
    	}
    	return ans;
    }
};
 
int main() {
//  freopen("rowords.in", "r", stdin); freopen("rowords.out", "w", stdout);
    string a, b;
    getline(cin, a);
    getline(cin, b);
    n = a.length();
    m = b.length();
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        s[i] = a.substr(i) + a.substr(0, i);
    }
    for (int i = 0; i < m; ++i) {
        t[i] = b.substr(i) + b.substr(0, i);
    }
    for (int i = 0; i < n && i < 10; ++i) {
        int curAns = 2;
        for (int j = 0; j < m; ++j) {
            if (ans <= curAns + 2) {
                curAns = LCS0SPOJ::lcs(s[i], t[j]);
                if (ans < curAns) {
                    ans = curAns;
                }
            }
            curAns += 2;
        }
    }
    cout << ans << '\n';
    return 0;
}

Subtask #1
72.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 584 KB Output is correct
5 Correct 3 ms 584 KB Output is correct
6 Correct 85 ms 1628 KB Output is correct
7 Execution timed out 2077 ms 2908 KB Time limit exceeded
8 Incorrect 508 ms 3076 KB Output isn't correct
9 Correct 542 ms 3076 KB Output is correct
10 Correct 705 ms 3076 KB Output is correct
11 Correct 1072 ms 3340 KB Output is correct
12 Correct 1821 ms 3796 KB Output is correct
13 Correct 563 ms 3796 KB Output is correct
14 Correct 748 ms 3420 KB Output is correct
15 Correct 1313 ms 3996 KB Output is correct
16 Correct 810 ms 3328 KB Output is correct
17 Incorrect 823 ms 3584 KB Output isn't correct
18 Correct 679 ms 4296 KB Output is correct
19 Correct 849 ms 3080 KB Output is correct
20 Incorrect 940 ms 3920 KB Output isn't correct
21 Correct 202 ms 4208 KB Output is correct
22 Correct 213 ms 4444 KB Output is correct
23 Correct 115 ms 4740 KB Output is correct
24 Incorrect 379 ms 5208 KB Output isn't correct
25 Incorrect 376 ms 5724 KB Output isn't correct