Submission #1107688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107688		Dukey	Necklace (Subtask 4) (BOI19_necklace4)	C++17	0 / 15	2 ms	2128 KiB

necklace

// Thanks to : TVA
// Strycks, L3, PAD, TVT, NGUYEN^2, Whisper
// My friends...
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pii pair<int, int>
#define plli pair<ll, int>
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define bit(mask, i) ((mask >> i) & 1)
#define fi first
#define se second
#define For(i, a, b) for(int i = (a) ; i <= (b) ; ++i)
#define Ford(i, b, a) for(int i = (b) ; i >= (a) ; --i)
#define FILE freopen(name".INP", "r", stdin); freopen(name".OUT", "w", stdout);
#define int long long

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using str = string;
using ld = long double;
using ull = unsigned long long;
using htype = unsigned long long;

template <class T> bool ckmin(T &a, const T &b) {return (a > b ? a = b, true : false); };
template <class T> bool ckmax(T &a, const T &b) {return (a < b ? a = b, true : false); };
template <class T> void compress(vector <T> &a) {sort(all(a)); a.resize(unique(all(a)) - a.begin()); };
template <class T> int getcom(vector<T> &a, T val) {return lower_bound(all(a), val) - a.begin() + 1; };

const ll mod = 1e9 + 7;                             /// MOD CHANGED

ll add(ll x, ll y){
    return (x + y) % mod;
}

ll sub(ll x, ll y){
    return ((x - y) % mod + mod) % mod;
}

ll mul(ll x, ll y){
    return (x * y) % mod;
}

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

const int dx[] = {-1, 0, 0, 1};
const int dy[] = {0, -1, 1, 0};
const char MOVE[] = {'U', 'L', 'R', 'D'};

const ll INFll = 0x3f3f3f3f3f3f3f3f;
const int INFin = 0x3f3f3f3f;

const int maxn = 3e2 + 5;                           /// MAXN CHANGED

const int maxv = 1e6 + 5;                         /// MAXV CHANGED

// s[0, n - 1]
vector <int> Zfun(str s){
    int n = s.size();
    vector <int> z(n, 0);
    for(int l = 0, r = 0, i = 1 ; i < n ; ++i){
        if(i <= r) z[i] = min(z[i - l], r - i + 1);
        
        while(i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];

        if(i + z[i] - 1 > r){
            l = i;
            r = i + z[i] - 1;
        }
    }

    return z;
}

vector <int> kmp(str s){
    int n = s.size();
    vector <int> pi(n, 0);
    for(int i = 1 ; i < n ; ++i){
        int len = pi[i - 1];
        while(len > 0 && s[i] != s[len]) len = pi[len - 1];
        pi[i] = len + (s[i] == s[len]);
    }

    return pi;
}

vector < vector<int> > autu(str s){
    vector <int> pi = kmp(s);
    int n = s.size() - 1;
    vector < vector<int> > nxt(n + 1, vector<int>(26, 0));

    For(len, 0, n){
        For(c, 0, 25){
            if(s[len] == (c + 'a')) nxt[len][c] = len + 1;
            else if(len > 0) nxt[len][c] = nxt[pi[len - 1]][c];
        }
    }

    return nxt;
}

#define piii pair<int, pii>

int lef[maxn][maxn], rig[maxn][maxn];

piii cal(str a, str b){
    str cur = "";
    Ford(i, a.size() - 1, 0){
        if(i != a.size()) cur = a[i] + cur;
        vector <int> pi = kmp(cur + '%' + b);
        For(j, 0, b.size() - 1){
            lef[j][i] = pi[cur.size() + 1 + j];
        }
    }

    cur = "";

    Ford(i, b.size() - 1, 0){
        if(i != b.size()) cur = b[i] + cur;
        vector <int> pi = kmp(cur + '%' + a);
        For(j, 0, a.size() - 1){
            rig[i][j] = pi[cur.size() + 1 + j];
        }
    }

    piii ans = {0, {0, 0}};

    For(i, 0, b.size()){
        For(j, 0, a.size()){
            int l = 0, r = 0;            
            if(i > 0) l = lef[i - 1][j];
            if(j > 0) r = rig[i][j - 1];

            if(ans.fi < l + r){
                ans.fi = l + r;
                ans.se = {j - r, i - l};
            }
        }
    }

    return ans;
}

signed main(){
    fast
    #define name "Anya"
    // FILE
    str a, b; cin >> a >> b;
    piii ans = cal(a, b);
    reverse(all(b));
    ckmax(ans, cal(a, b));
    cout << ans.fi << '\n';
    cout << ans.se.fi << " " << ans.se.se;
}

Compilation message (stderr)

necklace.cpp: In function 'std::pair<long long int, std::pair<long long int, long long int> > cal(str, str)':
necklace.cpp:114:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         if(i != a.size()) cur = a[i] + cur;
      |            ~~^~~~~~~~~~~
necklace.cpp:16:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 | #define For(i, a, b) for(int i = (a) ; i <= (b) ; ++i)
      |                                          ^
necklace.cpp:116:9: note: in expansion of macro 'For'
  116 |         For(j, 0, b.size() - 1){
      |         ^~~
necklace.cpp:124:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |         if(i != b.size()) cur = b[i] + cur;
      |            ~~^~~~~~~~~~~
necklace.cpp:16:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 | #define For(i, a, b) for(int i = (a) ; i <= (b) ; ++i)
      |                                          ^
necklace.cpp:126:9: note: in expansion of macro 'For'
  126 |         For(j, 0, a.size() - 1){
      |         ^~~
necklace.cpp:16:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 | #define For(i, a, b) for(int i = (a) ; i <= (b) ; ++i)
      |                                          ^
necklace.cpp:133:5: note: in expansion of macro 'For'
  133 |     For(i, 0, b.size()){
      |     ^~~
necklace.cpp:16:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 | #define For(i, a, b) for(int i = (a) ; i <= (b) ; ++i)
      |                                          ^
necklace.cpp:134:9: note: in expansion of macro 'For'
  134 |         For(j, 0, a.size()){
      |         ^~~

• Subtask 1: 0 / 15