oj.uz

Submission #933653

# Submission time Handle Problem Language Result Execution time Memory
933653 2024-02-26T04:07:09 Z mgch Round words (IZhO13_rowords) C++14
76 / 100
 346 ms 5768 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, tmp, 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 < 1; ++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
76.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 15 ms 1876 KB Output is correct
7 Correct 255 ms 2908 KB Output is correct
8 Incorrect 111 ms 3080 KB Output isn't correct
9 Correct 116 ms 2904 KB Output is correct
10 Correct 115 ms 2908 KB Output is correct
11 Correct 166 ms 3340 KB Output is correct
12 Correct 346 ms 3796 KB Output is correct
13 Correct 146 ms 3672 KB Output is correct
14 Correct 179 ms 3416 KB Output is correct
15 Correct 230 ms 4008 KB Output is correct
16 Correct 155 ms 3328 KB Output is correct
17 Incorrect 119 ms 3584 KB Output isn't correct
18 Correct 108 ms 4188 KB Output is correct
19 Correct 140 ms 3076 KB Output is correct
20 Incorrect 168 ms 3732 KB Output isn't correct
21 Correct 38 ms 4188 KB Output is correct
22 Correct 56 ms 4444 KB Output is correct
23 Correct 30 ms 4696 KB Output is correct
24 Incorrect 87 ms 5208 KB Output isn't correct
25 Incorrect 59 ms 5768 KB Output isn't correct