oj.uz

Submission #933664

# Submission time Handle Problem Language Result Execution time Memory
933664 2024-02-26T04:17:47 Z mgch Round words (IZhO13_rowords) C++14
76 / 100
 488 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);
    }
    sort(s, s + n);
    for (int i = 0; i < n && i < 2; ++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 1 ms 344 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 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 23 ms 1868 KB Output is correct
7 Correct 488 ms 3160 KB Output is correct
8 Incorrect 118 ms 2908 KB Output isn't correct
9 Correct 152 ms 2904 KB Output is correct
10 Correct 206 ms 2908 KB Output is correct
11 Correct 274 ms 3332 KB Output is correct
12 Correct 483 ms 3792 KB Output is correct
13 Correct 223 ms 3676 KB Output is correct
14 Correct 231 ms 3456 KB Output is correct
15 Correct 263 ms 4008 KB Output is correct
16 Correct 191 ms 3328 KB Output is correct
17 Incorrect 190 ms 3416 KB Output isn't correct
18 Correct 202 ms 4296 KB Output is correct
19 Correct 175 ms 3080 KB Output is correct
20 Incorrect 202 ms 3736 KB Output isn't correct
21 Correct 54 ms 4188 KB Output is correct
22 Correct 54 ms 4440 KB Output is correct
23 Correct 58 ms 4740 KB Output is correct
24 Incorrect 116 ms 5212 KB Output isn't correct
25 Incorrect 84 ms 5724 KB Output isn't correct