Submission #875834

#	Time	Username	Problem	Language	Result	Execution time	Memory
875834		sleepntsheep	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	5 / 85	214 ms	1940 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 = 984298797;
u64 B = 137;
u64 V[255];

u64 pown(u64 a, u64 b)
{
    u64 r = 1;
    for (int 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 function 'u64 pown(u64, u64)':
necklace.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'u64' {aka 'long long unsigned int'} [-Wsign-compare]
   29 |     for (int i = 1; i <= b; ++i) r = (r * a) % M;
      |                     ~~^~~~
necklace.cpp: In lambda function:
necklace.cpp:41:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   41 |         return u64(V[a]*V[b]^(V[a]+V[b]));
      |                      ^
necklace.cpp:41:27: warning: array subscript has type 'char' [-Wchar-subscripts]
   41 |         return u64(V[a]*V[b]^(V[a]+V[b]));
      |                           ^
necklace.cpp:41:33: warning: array subscript has type 'char' [-Wchar-subscripts]
   41 |         return u64(V[a]*V[b]^(V[a]+V[b]));
      |                                 ^
necklace.cpp:41:38: warning: array subscript has type 'char' [-Wchar-subscripts]
   41 |         return u64(V[a]*V[b]^(V[a]+V[b]));
      |                                      ^
necklace.cpp: In function 'int main()':
necklace.cpp:58:23: 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 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:58:66: 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 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:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i = 0; i < t.size(); ++i)
      |                     ~~^~~~~~~~~~
necklace.cpp:60:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for (int j = 1; j + i - 1 < t.size(); ++j)
      |                         ~~~~~~~~~~^~~~~~~~~~

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