답안 #503309

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
503309 2022-01-07T16:12:38 Z Victor Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
1500 ms 3180 KB
// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const ll INF = 1'000'000'007, MAXN = 3000;
const ll num_bases = 2, bases[] = {47, 31};
ll base_pow[num_bases][MAXN + 1], prefix_hash[3][num_bases][3001];

string jill, jane, revjane;

vll hash_val(int str, int pos, int len) {
    vll vals;
    rep(base, 0, num_bases) {
        ll rem = pos ? prefix_hash[str][base][pos - 1] : 0;
        rem = rem * base_pow[base][len] % INF;
        ll val = ((prefix_hash[str][base][pos + len - 1] - rem) % INF + INF) % INF;
        vals.pb(val);
    }
    return vals;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    rep(i, 0, num_bases) base_pow[i][0] = 1;
    rep(i, 0, num_bases) rep(j, 1, MAXN + 1) base_pow[i][j] = base_pow[i][j - 1] * bases[i] % INF;

    cin >> jill >> jane;
    trav(let, jill) let -= 'a';
    trav(let, jane) let -= 'a';
    revjane = jane;
    reverse(all(revjane));

    rep(i, 0, 3) {
        string str = jill;
        if (i == 1) str = jane;
        if (i == 2) str = revjane;
        rep(base, 0, num_bases) rep(j, 0, sz(str)) prefix_hash[i][base][j] = (str[j] + (j ? prefix_hash[i][base][j - 1] * bases[base] : 0)) % INF;
    }

    umap<ll, int> possible;
    int n = min(sz(jill), sz(jane));

    per(len, 1, n + 1) {
        rep(i, 0, sz(jill) - len + 1) {
            vll vals = hash_val(0, i, len);
            ll sum = 0, mult = 1;
            rep(base, 0, num_bases) {
                sum += vals[base] * mult;
                if (base + 1 != num_bases) mult *= INF;
            }
            possible.emplace(sum, i);
        }

        rep(j, 1, 3) {
            string str = jane;
            if (j == 2) str = revjane;

            rep(i, 0, sz(jane) - len + 1) {
                vll vals = hash_val(j, i, len);
                rep(k, 0, len) {
                    ll sum = 0, mult = 1;
                    rep(base, 0, num_bases) {
                        sum += vals[base] * mult;
                        if (base + 1 != num_bases) mult *= INF;
                    }

                    if (possible.count(sum)) {
                        int sjane = i;
                        if (j == 2) {
                            sjane = sz(jane) - sjane;
                            sjane -= len;
                        }
                        cout << len << endl
                             << possible[sum] << ' ' << sjane << endl;
                        return 0;
                    }

                    rep(base, 0, num_bases) {
                        vals[base] = ((vals[base] - base_pow[base][len - 1] * str[i + k]) % INF + INF) % INF;
                        vals[base] = (vals[base] * bases[base] + str[i + k]) % INF;
                    }
                }
            }
        }
    }

    return 0;
}

Compilation message

necklace.cpp: In function 'int main()':
necklace.cpp:8:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define rep(i, a, b) for (int i = (a); i < (b); ++i)
      |                                          ^
necklace.cpp:65:33: note: in expansion of macro 'rep'
   65 |         rep(base, 0, num_bases) rep(j, 0, sz(str)) prefix_hash[i][base][j] = (str[j] + (j ? prefix_hash[i][base][j - 1] * bases[base] : 0)) % INF;
      |                                 ^~~
necklace.cpp:8:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define rep(i, a, b) for (int i = (a); i < (b); ++i)
      |                                          ^
necklace.cpp:72:9: note: in expansion of macro 'rep'
   72 |         rep(i, 0, sz(jill) - len + 1) {
      |         ^~~
necklace.cpp:8:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define rep(i, a, b) for (int i = (a); i < (b); ++i)
      |                                          ^
necklace.cpp:86:13: note: in expansion of macro 'rep'
   86 |             rep(i, 0, sz(jane) - len + 1) {
      |             ^~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 7 ms 332 KB Output is correct
4 Correct 6 ms 460 KB Output is correct
5 Correct 15 ms 552 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 7 ms 332 KB Output is correct
4 Correct 6 ms 460 KB Output is correct
5 Correct 15 ms 552 KB Output is correct
6 Correct 39 ms 420 KB Output is correct
7 Correct 63 ms 448 KB Output is correct
8 Correct 323 ms 1816 KB Output is correct
9 Correct 622 ms 1444 KB Output is correct
10 Correct 879 ms 2776 KB Output is correct
11 Correct 945 ms 3180 KB Output is correct
12 Correct 631 ms 2016 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 7 ms 332 KB Output is correct
4 Correct 6 ms 460 KB Output is correct
5 Correct 15 ms 552 KB Output is correct
6 Correct 39 ms 420 KB Output is correct
7 Correct 63 ms 448 KB Output is correct
8 Correct 323 ms 1816 KB Output is correct
9 Correct 622 ms 1444 KB Output is correct
10 Correct 879 ms 2776 KB Output is correct
11 Correct 945 ms 3180 KB Output is correct
12 Correct 631 ms 2016 KB Output is correct
13 Execution timed out 1585 ms 788 KB Time limit exceeded
14 Halted 0 ms 0 KB -