Submission #479067

#	Time	Username	Problem	Language	Result	Execution time	Memory
479067		Green55	Round words (IZhO13_rowords)	C++17	28 / 100	2099 ms	37400 KiB

rowords

#include<bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()

#define uint unsigned long long
#define ull unsigned __int128

const int LEN = 64;
const int MAX = 3010 + LEN;

inline bool at(uint a[], int i){
    return a[i/LEN] & ((uint)1 << (i%LEN));
}

inline bool tog(uint a[], int i) {
    return a[i/LEN] ^= ((uint)1 << (i%LEN));
}

int n;
uint a[MAX/LEN], b[MAX/LEN], cs[26][MAX/LEN];

void solve(uint c[]){
    //sliding b -> a
    memcpy(a, b, sizeof(b));
    memset(b, 0, sizeof(b));
    
    // b = (a << 1) | 1
    uint carry = 1;
    for(int i=0; i<n/LEN; ++i) {
        b[i] = (a[i] << 1) | carry;
        carry = bool(a[i] & ((uint)1<<(LEN-1)));
    }

    // b = -b = ~b + 1
    for(int i=0; i<n/LEN; ++i) b[i] = ~b[i];
    for(int i=0; i<n; ++i) if(tog(b, i)) break;

    // a |= c, b += a, b &= a, b ^= a
    carry = 0;
    for(int i=0; i<n/LEN; ++i) {
        a[i] |= c[i];
        ull tmp = b[i]; tmp += a[i]; tmp += carry;
        b[i] = tmp & (~(uint)0);
        carry = tmp >> LEN;

        b[i] &= a[i];
        b[i] ^= a[i];
    }
}

int solve_tc(string s, string t) {
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    memset(cs, 0, sizeof(cs));

    // init c['A'] ~ c['Z']
    for(int i=0; i<t.size(); ++i) {
        tog(cs[t[i] - 'a'], i);
    }
    n = (t.size()/LEN+1)*LEN;

    for(int idx=0; idx<s.size(); ++idx) {
        char c = s[idx];
        solve(cs[c - 'a']);
    }

    int ret = 0;
    for(int i=0; i<t.size(); ++i){
        ret += at(b, i);
    }
    // cout << s << ' ' << t << " : " << ret << endl;
    return ret;
}

int dp[MAX][MAX];
void chk_naive(string s, string t, int ret) {
    memset(dp, 0, sizeof(dp));
    for(int i=1; i<=s.size(); ++i) {
        for(int j=1; j<=t.size(); ++j) {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            if(s[i-1] == t[j-1])
                dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1);
        }
    }
    if(dp[s.size()][t.size()] != ret) {
        cout << s << endl << t;
        exit(1);
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    string a, b;
    cin >> a >> b;
    for(char c : a) assert(islower(c));
    for(char c : b) assert(islower(c));
    // srand(4546);
    // for(int i=0; i<2000; ++i) a.push_back('a' + (rand()%26));
    // for(int i=0; i<2000; ++i) b.push_back('a' + (rand()%26));

    int ans = 0;
    for(int i=0; i<b.size(); ++i){
        int ret = solve_tc(a, b);
        chk_naive(a, b, ret);
        ans = max(ans, ret);
        b.push_back(b[0]);
        b.erase(b.begin());
    }
    cout << ans;
}

Compilation message (stderr)

rowords.cpp: In function 'int solve_tc(std::string, std::string)':
rowords.cpp:57:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i=0; i<t.size(); ++i) {
      |                  ~^~~~~~~~~
rowords.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int idx=0; idx<s.size(); ++idx) {
      |                    ~~~^~~~~~~~~
rowords.cpp:68:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i=0; i<t.size(); ++i){
      |                  ~^~~~~~~~~
rowords.cpp: In function 'void chk_naive(std::string, std::string, int)':
rowords.cpp:78:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int i=1; i<=s.size(); ++i) {
      |                  ~^~~~~~~~~~
rowords.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for(int j=1; j<=t.size(); ++j) {
      |                      ~^~~~~~~~~~
rowords.cpp: In function 'int main()':
rowords.cpp:103:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for(int i=0; i<b.size(); ++i){
      |                  ~^~~~~~~~~

• Subtask 1: 28 / 100