Submission #712375

#	Time	Username	Problem	Language	Result	Execution time	Memory
712375		gagik_2007	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	85 / 85	632 ms	608 KiB

necklace

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;

typedef long long ll;
typedef long double ld;

#define ff first
#define ss second

ll ttt;
const ll INF = 6e18;
const ll MOD = 1e9 + 7;
const ll N = 200007;
const ll LG = 21;
ll n, m, k;

vector<int>prefix_function(const string& s) {
    vector<int>pi = { 0 };
    for (int i = 1; i < s.size(); i++) {
        int j = pi[i - 1];
        while (j > 0 && s[j] != s[i]) {
            j = pi[j - 1];
        }
        if (s[j] == s[i]) {
            j++;
        }
        pi.push_back(j);
    }
    return pi;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s, t, rev, cur;
    cin >> s >> t;
    rev = t;
    reverse(rev.begin(), rev.end());
    int ans = 0;
    int vi = -1, vj = -1;
    for (int i = 0; i < s.size(); i++) {
        cur = "";
        for (int j = 0; j < i; j++) {
            cur += s[j];
        }
        vector<int>pi1(s.size() + t.size() + 1, 0), pi2(s.size() + t.size() + 1, 0);
        vector<int>p1, p2;
        if (cur != "") {
            reverse(cur.begin(), cur.end());
            pi1 = prefix_function(cur + '#' + rev);
            reverse(pi1.begin() + cur.size() + 1, pi1.end());
            for (int j = cur.size() + 1; j < pi1.size(); j++) {
                p1.push_back(pi1[j]);
            }
        }
        else {
            p1.resize(t.size(), 0);
        }
        cur = "";
        for (int j = i; j < s.size(); j++) {
            cur += s[j];
        }
        if (cur != "") {
            pi2 = prefix_function(cur + '#' + t);
            for (int j = cur.size() + 1; j < pi2.size(); j++) {
                p2.push_back(pi2[j]);
            }
        }
        else {
            p2.resize(t.size(), 0);
        }
        /*cout << i << endl;
        for (int x : p1) {
            cout << x << " ";
        }
        cout << endl;
        for (int x : p2) {
            cout << x << " ";
        }
        cout << endl;*/
        for (int j = 1; j < p1.size() && j - 1 < p2.size(); j++) {
            if (ans < p1[j] + p2[j - 1]) {
                //cout << i << " " << j << endl;
                ans = p1[j] + p2[j - 1];
                vi = i - p1[j];
                vj = j - p2[j - 1];
            }
        }
    }
    reverse(t.begin(), t.end());
    reverse(rev.begin(), rev.end());
    for (int i = 0; i < s.size(); i++) {
        cur = "";
        for (int j = 0; j < i; j++) {
            cur += s[j];
        }
        vector<int>pi1(s.size() + t.size() + 1, 0), pi2(s.size() + t.size() + 1, 0);
        vector<int>p1, p2;
        if (cur != "") {
            reverse(cur.begin(), cur.end());
            pi1 = prefix_function(cur + '#' + rev);
            reverse(pi1.begin() + cur.size() + 1, pi1.end());
            for (int j = cur.size() + 1; j < pi1.size(); j++) {
                p1.push_back(pi1[j]);
            }
        }
        else {
            p1.resize(t.size(), 0);
        }
        cur = "";
        for (int j = i; j < s.size(); j++) {
            cur += s[j];
        }
        if (cur != "") {
            pi2 = prefix_function(cur + '#' + t);
            for (int j = cur.size() + 1; j < pi2.size(); j++) {
                p2.push_back(pi2[j]);
            }
        }
        else {
            p2.resize(t.size(), 0);
        }
        /*cout << i << endl;
        for (int x : p1) {
            cout << x << " ";
        }
        cout << endl;
        for (int x : p2) {
            cout << x << " ";
        }
        cout << endl;*/
        for (int j = 1; j < p1.size() && j - 1 < p2.size(); j++) {
            if (ans < p1[j] + p2[j - 1]) {
                //cout << i << " " << j << endl;
                ans = p1[j] + p2[j - 1];
                vi = i - p1[j];
                vj = j - p2[j - 1];
                vj = t.size() - ans - vj;
            }
        }
    }
    cout << ans << endl;
    cout << vi << " " << vj << endl;
    return 0;
}

/// ---- - --------  ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - --------  ------ -------- -- - - -

Compilation message (stderr)

necklace.cpp: In function 'std::vector<int> prefix_function(const string&)':
necklace.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int i = 1; i < s.size(); i++) {
      |                     ~~^~~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for (int i = 0; i < s.size(); i++) {
      |                     ~~^~~~~~~~~~
necklace.cpp:72:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             for (int j = cur.size() + 1; j < pi1.size(); j++) {
      |                                          ~~^~~~~~~~~~~~
necklace.cpp:80:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for (int j = i; j < s.size(); j++) {
      |                         ~~^~~~~~~~~~
necklace.cpp:85:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             for (int j = cur.size() + 1; j < pi2.size(); j++) {
      |                                          ~~^~~~~~~~~~~~
necklace.cpp:101:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         for (int j = 1; j < p1.size() && j - 1 < p2.size(); j++) {
      |                         ~~^~~~~~~~~~~
necklace.cpp:101:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         for (int j = 1; j < p1.size() && j - 1 < p2.size(); j++) {
      |                                          ~~~~~~^~~~~~~~~~~
necklace.cpp:112:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for (int i = 0; i < s.size(); i++) {
      |                     ~~^~~~~~~~~~
necklace.cpp:123:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |             for (int j = cur.size() + 1; j < pi1.size(); j++) {
      |                                          ~~^~~~~~~~~~~~
necklace.cpp:131:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         for (int j = i; j < s.size(); j++) {
      |                         ~~^~~~~~~~~~
necklace.cpp:136:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |             for (int j = cur.size() + 1; j < pi2.size(); j++) {
      |                                          ~~^~~~~~~~~~~~
necklace.cpp:152:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |         for (int j = 1; j < p1.size() && j - 1 < p2.size(); j++) {
      |                         ~~^~~~~~~~~~~
necklace.cpp:152:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |         for (int j = 1; j < p1.size() && j - 1 < p2.size(); j++) {
      |                                          ~~~~~~^~~~~~~~~~~

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