oj.uz

답안 #503269

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
503269 2022-01-07T15:22:15 Z Victor Necklace (Subtask 1-3) (BOI19_necklace1) C++17
9 / 85
 1500 ms 388 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));

    int lo = 0, hi = n;
    int start_jill = 0, start_jane = 0;
    while (lo != hi) {
        int mid = (lo + hi + 1) / 2;

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

                    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));
        }

        if (sjill == -1)
            hi = mid - 1;
        else {
            lo = mid;
            start_jill = sjill;
            start_jane = sjane;
        }
        possible.clear();
    }

    cout << lo << endl;
    cout << start_jill << ' ' << start_jane << endl;

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

Subtask #1
5.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 356 KB Output is correct
2 Partially correct 1 ms 332 KB Output is partially correct
3 Correct 2 ms 364 KB Output is correct
4 Partially correct 2 ms 332 KB Output is partially correct
5 Correct 2 ms 340 KB Output is correct

Subtask #2
4.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 356 KB Output is correct
2 Partially correct 1 ms 332 KB Output is partially correct
3 Correct 2 ms 364 KB Output is correct
4 Partially correct 2 ms 332 KB Output is partially correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 17 ms 364 KB Output is correct
7 Partially correct 35 ms 332 KB Output is partially correct
8 Correct 24 ms 380 KB Output is correct
9 Partially correct 33 ms 376 KB Output is partially correct
10 Partially correct 29 ms 388 KB Output is partially correct
11 Partially correct 20 ms 380 KB Output is partially correct
12 Correct 22 ms 380 KB Output is correct

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 356 KB Output is correct
2 Partially correct 1 ms 332 KB Output is partially correct
3 Correct 2 ms 364 KB Output is correct
4 Partially correct 2 ms 332 KB Output is partially correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 17 ms 364 KB Output is correct
7 Partially correct 35 ms 332 KB Output is partially correct
8 Correct 24 ms 380 KB Output is correct
9 Partially correct 33 ms 376 KB Output is partially correct
10 Partially correct 29 ms 388 KB Output is partially correct
11 Partially correct 20 ms 380 KB Output is partially correct
12 Correct 22 ms 380 KB Output is correct
13 Execution timed out 1571 ms 332 KB Time limit exceeded
14 Halted 0 ms 0 KB -