Submission #596922

#	Time	Username	Problem	Language	Result	Execution time	Memory
596922		jy0n	Round words (IZhO13_rowords)	C++17	100 / 100	239 ms	296 KiB

rowords

#include <bits/stdc++.h>
using namespace std;
using ull=unsigned long long;

const int Sigma= 26;
string A, B;
vector<ull> d, s[Sigma];

#define set_bit(bs, i) (bs[i>>6] |= 1llu << (i&63))
#define get_bit(bs, i) ((bs[i>>6] >> (i&63))&1)
#define sub(a, b) ((a-b>a)? (a-=b, 1) : (a-=b, 0))

int main() {
    cin >> A >> B;
    int n = (int)A.size(), m = (int)B.size(), l = (m>>6)+1, ans=0;
    d.resize(l);
    for (int i=0; i<Sigma; ++i) s[i].resize(l);
    for (int i=0; i<m; ++i) set_bit(s[B[i]-'a'], i);
    for (int k=0; k<n; ++k) {
        memset(&d[0], 0, sizeof(ull)*l);
        for (int i=0; i<m; ++i) if (A[k] == B[i]) { set_bit(d, i); break; }
        for (int i=1; i<n; ++i) {
            ull sc = 1, mc = 0;
            for (int j=0; j<l; ++j) {
                ull x = s[A[(k+i)%n]-'a'][j]|d[j];
                ull t = (d[j] << 1)|sc;
                sc = d[j] >> 63;
                ull tt = x;
                mc = sub(tt, mc) + sub(tt, t);
                d[j] = x&(x^tt);
            }
        }
        int ret = 0;
        for (int i=0; i<m; ++i) ret += get_bit(d, i);
        ans=max(ans, ret);
    }
    for (int k=0; k<n; ++k) {
        memset(&d[0], 0, sizeof(ull)*l);
        for (int i=0; i<m; ++i) if (A[k] == B[i]) { set_bit(d, i); break; }
        for (int i=n-1; i>0; --i) {
            ull sc = 1, mc = 0;
            for (int j=0; j<l; ++j) {
                ull x = s[A[(k+i)%n]-'a'][j]|d[j];
                ull t = (d[j] << 1)|sc;
                sc = d[j] >> 63;
                ull tt = x;
                mc = sub(tt, mc) + sub(tt, t);
                d[j] = x&(x^tt);
            }
        }
        int ret = 0;
        for (int i=0; i<m; ++i) ret += get_bit(d, i);
        ans=max(ans, ret);
    }
    cout << ans << endl;
}

Compilation message (stderr)

rowords.cpp: In function 'int main()':
rowords.cpp:11:31: warning: operation on 'tt' may be undefined [-Wsequence-point]
   11 | #define sub(a, b) ((a-b>a)? (a-=b, 1) : (a-=b, 0))
......
   29 |                 mc = sub(tt, mc) + sub(tt, t);
      |                          ~~~~~~
rowords.cpp:29:22: note: in expansion of macro 'sub'
   29 |                 mc = sub(tt, mc) + sub(tt, t);
      |                      ^~~
rowords.cpp:11:31: warning: operation on 'tt' may be undefined [-Wsequence-point]
   11 | #define sub(a, b) ((a-b>a)? (a-=b, 1) : (a-=b, 0))
......
   47 |                 mc = sub(tt, mc) + sub(tt, t);
      |                          ~~~~~~
rowords.cpp:47:22: note: in expansion of macro 'sub'
   47 |                 mc = sub(tt, mc) + sub(tt, t);
      |                      ^~~

• Subtask 1: 100 / 100