oj.uz

Submission #933668

# Submission time Handle Problem Language Result Execution time Memory
933668 2024-02-26T04:22:51 Z mgch Round words (IZhO13_rowords) C++14
76 / 100
 359 ms 5888 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);
    swap(a, 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 344 KB Output isn't correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 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 64 ms 1848 KB Output is correct
7 Correct 255 ms 3072 KB Output is correct
8 Incorrect 89 ms 2904 KB Output isn't correct
9 Correct 130 ms 3080 KB Output is correct
10 Correct 139 ms 3076 KB Output is correct
11 Correct 184 ms 3348 KB Output is correct
12 Correct 359 ms 3920 KB Output is correct
13 Correct 118 ms 3676 KB Output is correct
14 Correct 174 ms 3460 KB Output is correct
15 Correct 226 ms 4004 KB Output is correct
16 Correct 154 ms 3332 KB Output is correct
17 Incorrect 238 ms 3636 KB Output isn't correct
18 Correct 144 ms 4348 KB Output is correct
19 Correct 138 ms 3076 KB Output is correct
20 Incorrect 177 ms 3776 KB Output isn't correct
21 Correct 182 ms 4188 KB Output is correct
22 Correct 140 ms 4748 KB Output is correct
23 Correct 185 ms 4700 KB Output is correct
24 Incorrect 162 ms 5208 KB Output isn't correct
25 Incorrect 150 ms 5888 KB Output isn't correct