Submission #875833

#	Time	Username	Problem	Language	Result	Execution time	Memory
875833		sleepntsheep	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	0 / 85	3 ms	456 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 H(char *s, int n)
{
    auto L = [&](char a, char b){
        return u64(a*b^(a+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()
{
    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 'int main()':
necklace.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     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:43:66: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     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:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (int i = 0; i < t.size(); ++i)
      |                     ~~^~~~~~~~~~
necklace.cpp:45:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for (int j = 1; j + i - 1 < t.size(); ++j)
      |                         ~~~~~~~~~~^~~~~~~~~~

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