oj.uz

Submission #503282

# Submission time Handle Problem Language Result Execution time Memory
503282 2022-01-07T15:29:46 Z Victor Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 1500 ms 588 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[] = {31, 47};
ll base_pow[num_bases][MAXN];

string jill, jane;

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) base_pow[i][j] = base_pow[i][j - 1] * bases[i] % INF;

    cin >> jill >> jane;

    map<ii, int> possible;
    int n = min(sz(jill), sz(jane));

    per(mid, 1, n + 1) {
        vll hash_val = {0, 0};
        rep(j, 0, num_bases) rep(i, 0, mid - 1) hash_val[j] = (hash_val[j] * bases[j] + jill[i]) % INF;
        rep(i, mid - 1, sz(jill)) {
            rep(j, 0, num_bases) hash_val[j] = (hash_val[j] * bases[j] + jill[i]) % INF;

            possible.insert({{hash_val[0], hash_val[1]}, i - mid + 1});
            rep(j, 0, num_bases) hash_val[j] = ((hash_val[j] - base_pow[j][mid - 1] * jill[i - mid + 1]) % INF + INF) % INF;
        }

        int sjill = -1, sjane = -1;
        rep(k, 0, 2) {
            hash_val = {0, 0};
            rep(j, 0, num_bases) rep(i, 0, mid - 1) hash_val[j] = (hash_val[j] * bases[j] + jane[i]) % INF;
            rep(i, mid - 1, sz(jane)) {
                rep(j, 0, num_bases) hash_val[j] = (hash_val[j] * bases[j] + jane[i]) % INF;

                vll tmp_val = hash_val;
                rep(j, 0, mid) {
                    if (possible.count({tmp_val[0], tmp_val[1]})) {
                        if (k) {
                            sjane = i - mid + 1;
                            sjane = sz(jane) - sjane;
                            sjane -= mid;
                        } else
                            sjane = i - mid + 1;
                        sjill = possible[{tmp_val[0], tmp_val[1]}];
                        cout<<mid<<endl<<sjill<<' '<<sjane<<endl;
                        return 0;
                    }

                    rep(base, 0, 2) {
                        tmp_val[base] = ((tmp_val[base] - base_pow[base][mid - 1] * jane[i - mid + 1 + j]) % INF + INF) % INF;
                        tmp_val[base] = (tmp_val[base] * bases[base] + jane[i - mid + 1 + j]) % INF;
                    }
                }

                rep(j, 0, num_bases) hash_val[j] = ((hash_val[j] - base_pow[j][mid - 1] * jane[i - mid + 1]) % INF + INF) % INF;
            }
            reverse(all(jane));
        }
        possible.clear();
    }

    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:52:9: note: in expansion of macro 'rep'
   52 |         rep(i, mid - 1, sz(jill)) {
      |         ^~~
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:63:13: note: in expansion of macro 'rep'
   63 |             rep(i, mid - 1, sz(jane)) {
      |             ^~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 10 ms 332 KB Output is correct
4 Correct 8 ms 364 KB Output is correct
5 Correct 19 ms 380 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 10 ms 332 KB Output is correct
4 Correct 8 ms 364 KB Output is correct
5 Correct 19 ms 380 KB Output is correct
6 Correct 51 ms 344 KB Output is correct
7 Correct 88 ms 360 KB Output is correct
8 Correct 418 ms 352 KB Output is correct
9 Correct 936 ms 360 KB Output is correct
10 Correct 1264 ms 588 KB Output is correct
11 Correct 1295 ms 360 KB Output is correct
12 Correct 844 ms 364 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 10 ms 332 KB Output is correct
4 Correct 8 ms 364 KB Output is correct
5 Correct 19 ms 380 KB Output is correct
6 Correct 51 ms 344 KB Output is correct
7 Correct 88 ms 360 KB Output is correct
8 Correct 418 ms 352 KB Output is correct
9 Correct 936 ms 360 KB Output is correct
10 Correct 1264 ms 588 KB Output is correct
11 Correct 1295 ms 360 KB Output is correct
12 Correct 844 ms 364 KB Output is correct
13 Execution timed out 1569 ms 356 KB Time limit exceeded
14 Halted 0 ms 0 KB -