Submission #875836

#	Time	Username	Problem	Language	Result	Execution time	Memory
875836		sleepntsheep	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	5 / 85	218 ms	4476 KiB

necklace

#include <iostream>
#include <map>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;

using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 200005

u64 M = 1000000009;
u64 B = 10007;
u64 V[255];

u64 pown(u64 a, u64 b)
{
    u64 r = 1;
    for (u64 i = 1; i <= b; ++i) r = (r * a) % M;
    return r;
}

void init()
{
    for (int i = 0; i < 255; ++i) V[i] = pown(B, i);
}

u64 H(char *s, int n)
{
    auto L = [&](char a, char b){ return u64(V[a]*V[b]^(V[a]+V[b])); };
    u64 h { L(s[0], s[n-1]) };
    for (int i = 1; i < n; ++i)
        h = (h * L(s[i-1], s[i])) % M;
    return h;
}

string s, t;
map<u64, int> x;
int z, zz, zzz;

int main()
{
    init();
    ShinLena;
    cin >> s >> t;
    for (int i = 0; i < s.size(); ++i) for (int j = 1; i + j - 1 < s.size(); ++j) x[H(s.data() + i, j)] = i;
    for (int i = 0; i < t.size(); ++i)
        for (int j = 1; j + i - 1 < t.size(); ++j)
        {
            u64 hh = H(t.data() + i, j);
            if (!x.count(hh)) continue;
            if (j > z)
                z = j, zz = x[hh], zzz = i;
        }
    cout << z << '\n' << zz << ' ' << zzz;

    return 0;
}

Compilation message (stderr)

necklace.cpp: In lambda function:
necklace.cpp:40:48: warning: array subscript has type 'char' [-Wchar-subscripts]
   40 |     auto L = [&](char a, char b){ return u64(V[a]*V[b]^(V[a]+V[b])); };
      |                                                ^
necklace.cpp:40:53: warning: array subscript has type 'char' [-Wchar-subscripts]
   40 |     auto L = [&](char a, char b){ return u64(V[a]*V[b]^(V[a]+V[b])); };
      |                                                     ^
necklace.cpp:40:59: warning: array subscript has type 'char' [-Wchar-subscripts]
   40 |     auto L = [&](char a, char b){ return u64(V[a]*V[b]^(V[a]+V[b])); };
      |                                                           ^
necklace.cpp:40:64: warning: array subscript has type 'char' [-Wchar-subscripts]
   40 |     auto L = [&](char a, char b){ return u64(V[a]*V[b]^(V[a]+V[b])); };
      |                                                                ^
necklace.cpp: In function 'int main()':
necklace.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (int i = 0; i < s.size(); ++i) for (int j = 1; i + j - 1 < s.size(); ++j) x[H(s.data() + i, j)] = i;
      |                     ~~^~~~~~~~~~
necklace.cpp:56:66: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (int i = 0; i < s.size(); ++i) for (int j = 1; i + j - 1 < s.size(); ++j) x[H(s.data() + i, j)] = i;
      |                                                        ~~~~~~~~~~^~~~~~~~~~
necklace.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int i = 0; i < t.size(); ++i)
      |                     ~~^~~~~~~~~~
necklace.cpp:58:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for (int j = 1; j + i - 1 < t.size(); ++j)
      |                         ~~~~~~~~~~^~~~~~~~~~

• Subtask 1: 5 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40