oj.uz

답안 #875833

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
875833 2023-11-20T15:15:10 Z sleepntsheep Necklace (Subtask 1-3) (BOI19_necklace1) C++17
0 / 85
 3 ms 456 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 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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Incorrect 2 ms 344 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Incorrect 2 ms 344 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Incorrect 2 ms 344 KB Output isn't correct
5 Halted 0 ms 0 KB -