oj.uz

Submission #245227

# Submission time Handle Problem Language Result Execution time Memory
245227 2020-07-05T19:23:14 Z junseo 구간 성분 (KOI15_interval) C++17
100 / 100
 340 ms 25300 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]];
    }

    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

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.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 5 ms 512 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2164 KB Output is correct
2 Correct 27 ms 2540 KB Output is correct
3 Correct 16 ms 2540 KB Output is correct
4 Correct 14 ms 2540 KB Output is correct
5 Correct 35 ms 2540 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 8412 KB Output is correct
2 Correct 142 ms 8540 KB Output is correct
3 Correct 142 ms 8412 KB Output is correct
4 Correct 135 ms 8412 KB Output is correct
5 Correct 143 ms 8412 KB Output is correct
6 Correct 139 ms 8412 KB Output is correct
7 Correct 139 ms 8412 KB Output is correct
8 Correct 140 ms 8412 KB Output is correct
9 Correct 142 ms 8412 KB Output is correct
10 Correct 140 ms 8412 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 13020 KB Output is correct
2 Correct 309 ms 25300 KB Output is correct
3 Correct 287 ms 25280 KB Output is correct
4 Correct 156 ms 25300 KB Output is correct
5 Correct 340 ms 25300 KB Output is correct