oj.uz

Submission #875834

# Submission time Handle Problem Language Result Execution time Memory
875834 2023-11-20T15:16:28 Z sleepntsheep Necklace (Subtask 1-3) (BOI19_necklace1) C++17
5 / 85
 214 ms 1940 KB 
#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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 344 KB Output is partially correct
2 Partially correct 4 ms 348 KB Output is partially correct
3 Partially correct 3 ms 620 KB Output is partially correct
4 Partially correct 4 ms 604 KB Output is partially correct
5 Partially correct 5 ms 604 KB Output is partially correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 344 KB Output is partially correct
2 Partially correct 4 ms 348 KB Output is partially correct
3 Partially correct 3 ms 620 KB Output is partially correct
4 Partially correct 4 ms 604 KB Output is partially correct
5 Partially correct 5 ms 604 KB Output is partially correct
6 Partially correct 208 ms 972 KB Output is partially correct
7 Incorrect 214 ms 1940 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 344 KB Output is partially correct
2 Partially correct 4 ms 348 KB Output is partially correct
3 Partially correct 3 ms 620 KB Output is partially correct
4 Partially correct 4 ms 604 KB Output is partially correct
5 Partially correct 5 ms 604 KB Output is partially correct
6 Partially correct 208 ms 972 KB Output is partially correct
7 Incorrect 214 ms 1940 KB Output isn't correct
8 Halted 0 ms 0 KB -