oj.uz

Submission #862364

# Submission time Handle Problem Language Result Execution time Memory
862364 2023-10-18T06:22:05 Z iskhakkutbilim Necklace (Subtask 1-3) (BOI19_necklace1) C++17
5 / 85
 1500 ms 944 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;
		if(check(mid)){
			l = mid;
			ANS = start;
		}else r = mid;
	}
//	if(l == 0) 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 3 ms 344 KB Output is correct
2 Partially correct 3 ms 348 KB Output is partially correct
3 Correct 14 ms 452 KB Output is correct
4 Partially correct 18 ms 348 KB Output is partially correct
5 Correct 20 ms 348 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Partially correct 3 ms 348 KB Output is partially correct
3 Correct 14 ms 452 KB Output is correct
4 Partially correct 18 ms 348 KB Output is partially correct
5 Correct 20 ms 348 KB Output is correct
6 Correct 72 ms 348 KB Output is correct
7 Partially correct 273 ms 344 KB Output is partially correct
8 Correct 1474 ms 944 KB Output is correct
9 Partially correct 1408 ms 448 KB Output is partially correct
10 Partially correct 1176 ms 348 KB Output is partially correct
11 Partially correct 1141 ms 440 KB Output is partially correct
12 Execution timed out 1541 ms 440 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Partially correct 3 ms 348 KB Output is partially correct
3 Correct 14 ms 452 KB Output is correct
4 Partially correct 18 ms 348 KB Output is partially correct
5 Correct 20 ms 348 KB Output is correct
6 Correct 72 ms 348 KB Output is correct
7 Partially correct 273 ms 344 KB Output is partially correct
8 Correct 1474 ms 944 KB Output is correct
9 Partially correct 1408 ms 448 KB Output is partially correct
10 Partially correct 1176 ms 348 KB Output is partially correct
11 Partially correct 1141 ms 440 KB Output is partially correct
12 Execution timed out 1541 ms 440 KB Time limit exceeded
13 Halted 0 ms 0 KB -