Submission #933670

#	Time	Username	Problem	Language	Result	Execution time	Memory
933670		mgch	Round words (IZhO13_rowords)	C++14	76 / 100	339 ms	5720 KiB

rowords

#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;
        }
        for (int j = 0; j < m; ++j) {
            reverse(t[j].begin(), t[j].end());
        }
    }
    cout << ans << '\n';
    return 0;
}

• Subtask 1: 76 / 100