Submission #479066

#	Time	Username	Problem	Language	Result	Execution time	Memory
479066		Green55	Round words (IZhO13_rowords)	C++17	76 / 100	164 ms	332 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 = 2205 + 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;
string s, t;
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<n; ++i){
        ret += at(b, i);
    }
    // cout << s << ' ' << t << " : " << ret << endl;
    return ret;
}

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));
    int ans = 0;
    for(int i=0; i<b.size(); ++i){
        ans = max(ans, solve_tc(a, b));
        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:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i=0; i<t.size(); ++i) {
      |                  ~^~~~~~~~~
rowords.cpp:63:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int idx=0; idx<s.size(); ++idx) {
      |                    ~~~^~~~~~~~~
rowords.cpp: In function 'int main()':
rowords.cpp:84:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int i=0; i<b.size(); ++i){
      |                  ~^~~~~~~~~

• Subtask 1: 76 / 100