oj.uz

Submission #245226

# Submission time Handle Problem Language Result Execution time Memory
245226 2020-07-05T19:19:55 Z junseo 구간 성분 (KOI15_interval) C++17
0 / 100
 415 ms 25292 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define ends ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define eb emplace_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

inline void rmin(int& r, int x) { r = min(r, x); }
inline void rmax(int& r, int x) { r = max(r, x); }

const ll mod = 1e9 + 7;
const int maxn = 1510;

ll prime[] = {1553543355441,6835413543356,341238467843,5846878493734,255654493854,4385646055553,29333247254,56842665466513,6562454444132,33264680204,97185465094454,8937264644356,85143166465423,78565446465415,98746146556215,8547654654856,841537879874131,7293864657254,9814378779242,74464658844594,24495564314761,186549524066569,39665654465873,481654731322,41565458484,13646542908};

int n, m;
ll as[maxn], bs[maxn], ax[maxn], bx[maxn];
string a, b;

int main(void) {
    ios_base::sync_with_stdio(0);   cin.tie(0);
    cin >> a >> b;
    n = a.size(), m = b.size();
    a = ' ' + a, b = ' ' + b;

    for(auto& c : a)    c -= 'a';
    for(auto& c : b)    c -= 'a';

    as[0] = bs[0] = 0;
    ax[0] = bx[0] = 0;

    for(int i = 1; i <= n; ++i) {
        as[i] = as[i - 1] + prime[a[i]];
        ax[i] = ax[i - 1] ^ prime[a[i]];
        as[i] %= mod;
    }

    for(int i = 1; i <= m; ++i) {
        bs[i] = bs[i - 1] + prime[b[i]];
        bx[i] = bx[i - 1] ^ prime[b[i]];
        bs[i] %= mod;
    }

    vector<ll> c, d;
    for(int i = 1; i <= n; ++i) for(int j = i; j <= n; ++j) {
        c.eb(as[j] - as[i - 1]);
        d.eb(ax[j] ^ ax[i - 1]);
    }
    sort(all(c));
    sort(all(d));

    int ans = 0;
    for(int i = 1; i <= n; ++i) for(int j = 1; i + j - 1 <= m; ++j) {
        if(binary_search(all(c), bs[i + j - 1] - bs[j - 1]) && binary_search(all(d), bx[i + j - 1] ^ bx[j - 1])) {
            ans = i;
            break;
        }
    }
    cout << ans;
    return 0;
}

Compilation message

interval.cpp: In function 'int main()':
interval.cpp:38:39: warning: array subscript has type 'char' [-Wchar-subscripts]
         as[i] = as[i - 1] + prime[a[i]];
                                       ^
interval.cpp:39:39: warning: array subscript has type 'char' [-Wchar-subscripts]
         ax[i] = ax[i - 1] ^ prime[a[i]];
                                       ^
interval.cpp:44:39: warning: array subscript has type 'char' [-Wchar-subscripts]
         bs[i] = bs[i - 1] + prime[b[i]];
                                       ^
interval.cpp:45:39: warning: array subscript has type 'char' [-Wchar-subscripts]
         bx[i] = bx[i - 1] ^ prime[b[i]];
                                       ^

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Incorrect 6 ms 512 KB Output isn't correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 2164 KB Output is correct
2 Incorrect 32 ms 2540 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 182 ms 8412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 13020 KB Output is correct
2 Incorrect 415 ms 25292 KB Output isn't correct
3 Halted 0 ms 0 KB -