oj.uz

답안 #479067

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
479067 2021-10-09T21:10:27 Z Green55 원형 문자열 (IZhO13_rowords) C++17
28 / 100
 2000 ms 37400 KB 
#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

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 46 ms 37196 KB Output isn't correct
2 Correct 60 ms 37292 KB Output is correct
3 Correct 96 ms 37316 KB Output is correct
4 Correct 246 ms 37280 KB Output is correct
5 Correct 162 ms 37280 KB Output is correct
6 Correct 461 ms 37292 KB Output is correct
7 Execution timed out 2085 ms 37296 KB Time limit exceeded
8 Execution timed out 2098 ms 37244 KB Time limit exceeded
9 Execution timed out 2099 ms 37196 KB Time limit exceeded
10 Execution timed out 2098 ms 37208 KB Time limit exceeded
11 Execution timed out 2083 ms 37196 KB Time limit exceeded
12 Execution timed out 2085 ms 37200 KB Time limit exceeded
13 Execution timed out 2078 ms 37204 KB Time limit exceeded
14 Execution timed out 2094 ms 37256 KB Time limit exceeded
15 Execution timed out 2090 ms 37196 KB Time limit exceeded
16 Execution timed out 2091 ms 37196 KB Time limit exceeded
17 Execution timed out 2080 ms 37196 KB Time limit exceeded
18 Execution timed out 2090 ms 37236 KB Time limit exceeded
19 Execution timed out 2097 ms 37196 KB Time limit exceeded
20 Execution timed out 2091 ms 37196 KB Time limit exceeded
21 Correct 810 ms 37196 KB Output is correct
22 Correct 1531 ms 37196 KB Output is correct
23 Execution timed out 2085 ms 37296 KB Time limit exceeded
24 Execution timed out 2071 ms 37400 KB Time limit exceeded
25 Execution timed out 2087 ms 37196 KB Time limit exceeded