oj.uz

Submission #596903

# Submission time Handle Problem Language Result Execution time Memory
596903 2022-07-15T09:08:02 Z jy0n Round words (IZhO13_rowords) C++17
16 / 100
 158 ms 296 KB 
#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)*d.size());
        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 x : d) ret += __builtin_popcountll(x);
        ans=max(ans, ret);
    }
    cout << ans << endl;
}

Compilation message

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);
      |                      ^~~

Subtask #1
16.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Incorrect 13 ms 296 KB Output isn't correct
7 Correct 62 ms 212 KB Output is correct
8 Incorrect 78 ms 284 KB Output isn't correct
9 Incorrect 101 ms 284 KB Output isn't correct
10 Incorrect 78 ms 284 KB Output isn't correct
11 Incorrect 111 ms 288 KB Output isn't correct
12 Incorrect 115 ms 288 KB Output isn't correct
13 Incorrect 158 ms 284 KB Output isn't correct
14 Incorrect 114 ms 280 KB Output isn't correct
15 Incorrect 125 ms 284 KB Output isn't correct
16 Incorrect 73 ms 212 KB Output isn't correct
17 Incorrect 123 ms 280 KB Output isn't correct
18 Incorrect 114 ms 284 KB Output isn't correct
19 Incorrect 59 ms 212 KB Output isn't correct
20 Incorrect 90 ms 284 KB Output isn't correct
21 Incorrect 40 ms 280 KB Output isn't correct
22 Incorrect 55 ms 280 KB Output isn't correct
23 Incorrect 82 ms 284 KB Output isn't correct
24 Incorrect 110 ms 280 KB Output isn't correct
25 Incorrect 113 ms 284 KB Output isn't correct