Submission #245227

#	Time	Username	Problem	Language	Result	Execution time	Memory
245227		junseo	구간 성분 (KOI15_interval)	C++17	100 / 100	340 ms	25300 KiB

interval

#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]];
    }

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

    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 (stderr)

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:43:39: warning: array subscript has type 'char' [-Wchar-subscripts]
         bs[i] = bs[i - 1] + prime[b[i]];
                                       ^
interval.cpp:44:39: warning: array subscript has type 'char' [-Wchar-subscripts]
         bx[i] = bx[i - 1] ^ prime[b[i]];
                                       ^

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 31 / 31
• Subtask 4: 39 / 39