Submission #585274

#	Time	Username	Problem	Language	Result	Execution time	Memory
585274		ImtiazCho	Necklace (Subtask 4) (BOI19_necklace4)	C++17	15 / 15	196 ms	400 KiB

necklace

/** Bismillahir Rahmanir Rahim **/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pf push_front
#define endl '\n'
#define fi first
#define se second
#define ull unsigned ll
#define lld long double
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define Fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define debug(...) cerr << "[" << #__VA_ARGS__ << "] =>", dbg_out(__VA_ARGS__)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type>
ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Up, typename... Down> void dbg_out(Up U, Down... D) { cerr << ' ' << U; dbg_out(D...); }

template<typename T> bool chkmin(T &a, T b){return b < a ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return b > a ? a = b, 1 : 0;}

string a, b;
int ans = 0, l_idx,l_idx1;
vector<int> kmp(const string &b, const string &a) {
    // generating prefix function
    int m = sz(b);
    vector<int> pi(m);
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && b[i] != b[j]) j = pi[j - 1];
        if (b[i] == b[j]) j++;
        pi[i] = j;
    }

    // genarating chk
    int n = sz(a);
    vector<int> chk(n, 0);
    for (int i = 0, j = 0; i < n; i++) {
        while (j > 0 && a[i] != b[j]) j = pi[j - 1];
        if (a[i] == b[j]) {
            j++;
            chk[i] = j;
            if (j == m) j = pi[j - 1];
        }
    }

    return chk;
}

void solve() {
    cin >> a >> b;

    string br = b;
    reverse(all(br));

    // int turn = 2;
    int n = sz(a);
    int m = sz(b);

    // while (turn--) {
    //     for (int i = 0; i < n; i++) {

    //         string left = s.substr(0, i);
    //         reverse(all(left));

    //         string right = s.substr(i, n - i);

    //         vector<int> chk = kmp(t, right);
    //         debug(t, right);
    //         vector<int> chk1 = kmp(tr, left);
    //         debug(tr, left);
    //         reverse(all(chk1));
    //         int cnt = 0;
    //         for (int j = 0; j < sz(chk1); j++) {
    //             if (chk1[j]) {
    //                 cnt++;
    //                 chk1[j] = cnt;
    //                 continue;
    //             } 
    //             cnt = 0;
    //         }

    //         int len = 0;
    //         for (int j = 0; j < m; j++) {
    //             int len_right = chk[j];
    //             int pos = j - len_right;
    //             int len_left = chk1[pos];
    //             debug(len_right, pos, len_left);
    //             if (len_right + len_left > ans) {
    //                 ans = len_right + len_left;
    //                 l_idx = (i - chk1[j]);
    //                 l_idx1 = (j - chk1[j]);
    //             }
    //         }

    //         for (int j = 0; j < m; j++) {
    //             int len_right = chk1[j];
    //             int pos = j - len_right;
    //             int len_left = chk[pos];

    //             if (len_right + len_left > ans) {
    //                 ans = len_right + len_left;
    //                 l_idx = (i - chk1[j]);
    //                 l_idx1 = (m - (j + 1));
    //             }
    //         }

    //     }


    //     swap(t, tr);
    // }
    // cout << ans << endl;
    // cout << l_idx << " " << l_idx1 << endl;
    int ans = 0, cuta, cutb;
	for(int cas = 1; cas <= 2; cas++){
		for(int i = 0; i < n; i++){	// reverse before i
			string s1 = a.substr(i, n - i), s2 = a.substr(0, i);
			vector<int> l, r;
			l = kmp(s1, b);
 
			reverse(s2.begin(), s2.end());
			r = kmp(s2, br);
			reverse(r.begin(), r.end());

 
			if(chkmax(ans, r[0]))
				cuta = i - r[0], cutb = (cas == 1 ? 0 : m - r[0]);
			if(chkmax(ans, l[m - 1]))
				cuta = i, cutb = (cas == 1 ? m - l[m - 1] : 0);
			for(int j = 0; j < m - 1; j++)
				if(chkmax(ans, l[j] + r[j + 1]))
					cuta = i - r[j + 1], cutb = (cas == 1? j - l[j] + 1: m - j - r[j + 1] - 1);
		}
		swap(b, br);
	}
 
	cout << ans << endl;
	cout << cuta << " " << cutb << endl;
}
int main()
{
   Fastio;
   int tt = 1; 
//    cin >> tt;
   while (tt--) solve();

   return 0;
}

Compilation message (stderr)

necklace.cpp: In function 'void solve()':
necklace.cpp:7:14: warning: 'cutb' may be used uninitialized in this function [-Wmaybe-uninitialized]
    7 | #define endl '\n'
      |              ^~~~
necklace.cpp:119:24: note: 'cutb' was declared here
  119 |     int ans = 0, cuta, cutb;
      |                        ^~~~
necklace.cpp:143:18: warning: 'cuta' may be used uninitialized in this function [-Wmaybe-uninitialized]
  143 |  cout << cuta << " " << cutb << endl;
      |                  ^~~

• Subtask 1: 15 / 15