Submission #479073

#	Time	Username	Problem	Language	Result	Execution time	Memory
479073		Green55	Round words (IZhO13_rowords)	C++17	100 / 100	303 ms	344 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;
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);
    }
    return ret;
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
 
    string a, b;
    cin >> a >> b;
    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());
    }
    reverse(all(b));
    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: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: In function 'int main()':
rowords.cpp:80:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int i=0; i<b.size(); ++i){
      |                  ~^~~~~~~~~
rowords.cpp:86:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(int i=0; i<b.size(); ++i){
      |                  ~^~~~~~~~~

• Subtask 1: 100 / 100