Submission #153078

#	Time	Username	Problem	Language	Result	Execution time	Memory
153078		admin	Round words (IZhO13_rowords)	C++14	100 / 100	186 ms	504 KiB

rowords

#include <bits/stdc++.h>

#define get(arr, x) (((arr[x >> 6] >> (x & 63)) & 1) == 1)
#define set(arr, x) (arr[x >> 6] |= 1llu << (x & 63))
using ulint = unsigned long long;

int lcs(std::string A, std::string B) {
  int N = A.size(), M = B.size();
  int sz = (M >> 6) + 1;

  std::vector<ulint> S[256];
  for(int c = 0; c < 256; c++) S[c].resize(sz);
  for(int j = 0; j < M; j++) set(S[B[j]], j);
  
  std::vector<ulint> row(sz);
  for(int j = 0; j < M; j++) if(A[0] == B[j]) { set(row, j); break; }

  for(int i = 1; i < N; i++) {
    ulint shl_carry = 1;
    ulint minus_carry = 0;
    
    for(int k = 0; k < sz; k++) {
      // Compute k-th block of x == S[A[i]] OR M[i-1]
      ulint x_k = S[A[i]][k] | row[k];

      // Compute k-th block of "(M[i-1] << 1) | 1"
      ulint term_1 = (row[k] << 1) | shl_carry;
      shl_carry = row[k] >> 63;

      // Compute k-th block of "x - ((M[i-1] << 1) | 1)"
      auto sub_carry = [](ulint &x, ulint y){
        ulint tmp = x;
        return (x = tmp - y) > tmp;
      };
      ulint term_2 = x_k;
      minus_carry = sub_carry(term_2, minus_carry);
      minus_carry += sub_carry(term_2, term_1);
      
      row[k] = x_k & (x_k ^ term_2);
    }

    row[M >> 6] &= (1llu << (M & 63)) - 1;
  }

  int ret = 0;
  for(int j = 0; j < M; j++) if(get(row, j)) ret += 1;
  return ret;
}

int main() {
  std::string a, b;
  std::cin >> a >> b;

  int ans = 0;
  
  for(int rep = 0; rep < 2; rep++) {
    for(int i = 0; i < int(b.size()); i++) {
      ans = std::max(ans, lcs(a, b));
      std::rotate(b.begin(), b.begin() + 1, b.end());
    }
    std::reverse(b.begin(), b.end());
  }
  std::cout << ans << std::endl;
  return 0;
}

Compilation message (stderr)

rowords.cpp: In function 'int lcs(std::__cxx11::string, std::__cxx11::string)':
rowords.cpp:13:40: warning: array subscript has type 'char' [-Wchar-subscripts]
   for(int j = 0; j < M; j++) set(S[B[j]], j);
                                        ^
rowords.cpp:4:22: note: in definition of macro 'set'
 #define set(arr, x) (arr[x >> 6] |= 1llu << (x & 63))
                      ^~~
rowords.cpp:24:25: warning: array subscript has type 'char' [-Wchar-subscripts]
       ulint x_k = S[A[i]][k] | row[k];
                         ^

• Subtask 1: 100 / 100