oj.uz

Submission #862367

# Submission time Handle Problem Language Result Execution time Memory
862367 2023-10-18T06:27:02 Z iskhakkutbilim Necklace (Subtask 1-3) (BOI19_necklace1) C++17
5 / 85
 1500 ms 456 KB 
#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 401;

vector<int> z_function(string s){
	int n =(int)s.size();
	vector<int> z(n);
	for(int i=1, l=0, r=0; i<n; ++i){
		if(i <= r)
			z[i] = min (r-i+1, z[i-l]);
		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;
}

int has_sub(string a, string b){
	vector<int> z = z_function(b + "#" + a);
	for(int i = b.size() + 1; i < z.size(); i++){
		if(z[i] == b.size()) return 1;
	}
	return 0;
}


int good(string a, string b){
	if(has_sub(a + a, b)) return 1;
	reverse(all(b));
	if(has_sub(a + a, b)) return 1;
	return 0;
}
string s, t;
int n,m;
pair<int, int> start;
int check(int len){
	if(len > min(n, m)) return 0;
	if(len== 0) return 1;
	string A = "";
	for(int idx = 0; idx < len; idx++) A+= s[idx];
	for(int i = 0;i + len-1 < n; i++){
		string B = "";
		for(int idx = 0; idx < len; idx++) B+= t[idx];
		for(int j = 0;j + len-1 < m; j++){
			if(good(A, B)){
				start = {i, j};
				return 1;
			}
			B.erase(B.begin());
			if(j + len < m) B.push_back(t[j + len]);
		}
		if(i + len < n)A.push_back(s[i + len]);
		A.erase(A.begin());
	}
	return 0;
}

/*
int PA[N + 1][26], PB[N+1][26];
int getA(int l, int r, char ch){
	return PA[r][ch]-(l > 0 ? PA[l-1][ch] : 0);	
}

int getB(int l, int r, int ch){
	return PB[r][ch]-(l > 0 ? PB[l-1][ch] : 0);	
}
for(int i = 0;i < n; i++){
	for(int j = 0;j < 26; j++){
		PA[i][j] = (i > 0 ? PA[i-1][j] : 0);
		if(s[i]-'a' == j) PA[i][j]++;
	}
}
for(int i = 0;i < m; i++){
	for(int j = 0;j < 26; j++){
		PB[i][j] = (i > 0 ? PB[i-1][j] : 0);
		if(t[i]-'a' == j) PB[i][j]++;
	}
}*/
main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
	cin >> s >> t;
	n = s.size();
	m = t.size();

	int l = 0, r = min(n, m) + 1;
	pair<int, int> ANS = {-1, -1};
	while(l + 1 < r){
		int mid = (l + r) >> 1;
		start = {-1, -1};
		if(check(mid)){
			l = mid;
			ANS = start;
		}else r = mid;
	}
	if(l < 2) assert(false);
	cout << l << '\n';
	if(ANS.ff == -1) assert(false);
	cout << ANS.ff << ' ' << ANS.ss;
	return 0;
}

Compilation message

necklace.cpp: In function 'int has_sub(std::string, std::string)':
necklace.cpp:25:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for(int i = b.size() + 1; i < z.size(); i++){
      |                            ~~^~~~~~~~~~
necklace.cpp:26:11: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   if(z[i] == b.size()) return 1;
necklace.cpp: At global scope:
necklace.cpp:84:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   84 | main(){
      | ^~~~

Subtask #1
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Partially correct 3 ms 348 KB Output is partially correct
3 Correct 15 ms 456 KB Output is correct
4 Partially correct 19 ms 348 KB Output is partially correct
5 Correct 21 ms 344 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Partially correct 3 ms 348 KB Output is partially correct
3 Correct 15 ms 456 KB Output is correct
4 Partially correct 19 ms 348 KB Output is partially correct
5 Correct 21 ms 344 KB Output is correct
6 Correct 80 ms 452 KB Output is correct
7 Partially correct 274 ms 448 KB Output is partially correct
8 Execution timed out 1570 ms 348 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Partially correct 3 ms 348 KB Output is partially correct
3 Correct 15 ms 456 KB Output is correct
4 Partially correct 19 ms 348 KB Output is partially correct
5 Correct 21 ms 344 KB Output is correct
6 Correct 80 ms 452 KB Output is correct
7 Partially correct 274 ms 448 KB Output is partially correct
8 Execution timed out 1570 ms 348 KB Time limit exceeded
9 Halted 0 ms 0 KB -