oj.uz

Submission #130323

# Submission time Handle Problem Language Result Execution time Memory
130323 2019-07-14T20:05:18 Z thiago4532 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
25 / 85
 1500 ms 384 KB 
#include <bits/stdc++.h>

using namespace std;
string s, t;

int main() {
	cin >> s >> t;
	// cout << "\n" << s << "\n";
	// cout << t << "\n";

	int maximo = 0;
	int ini, fim;
	for(int i = 0; i < s.size(); i++) {
		for(int j = 0; j < t.size(); j++) { 
			int b_a=0, b_b=0;

			// while(i - a >= 0 && j + a <= t.size() && i + b <= s.size() && j - b >= 0 &&
			// 	s[i - a] == t[j + a - 1] && s[i + b - 1] == t[])		

			for(int a = 1; i - a >= 0 && j + a <= t.size(); a++) {
				// cout << a << "\n";
				if(a == 2 && i == 5 && j == 4) {
					// cout << s.substr(i-a, a) << "\n";
					// cout << t.substr(j, a) << "\n";
				}
				if(s.substr(i-a, a) == t.substr(j, a))
					b_a = a;
			}
			for(int b = 1; i + b <= s.size() && j - b >= 0; b++) {
				if(s.substr(i, b) == t.substr(j - b, b))
					b_b = b;
			}

			// if(b_a != 0 && b_b != 0) cout << b_a << " " << b_b << ": " << b_a + b_b << "\n";
			if(b_a + b_b > maximo) {
				maximo = b_a + b_b;
				ini = i - b_a;
				fim = j - b_b;
			}
		}
	}
	reverse(t.begin(), t.end());
	for(int i = 0; i < s.size(); i++) {
		for(int j = 0; j < t.size(); j++) { 
			int b_a=0, b_b=0;

			// while(i - a >= 0 && j + a <= t.size() && i + b <= s.size() && j - b >= 0 &&
			// 	s[i - a] == t[j + a - 1] && s[i + b - 1] == t[])		

			for(int a = 1; i - a >= 0 && j + a <= t.size(); a++) {
				// cout << a << "\n";
				if(a == 2 && i == 5 && j == 4) {
					// cout << s.substr(i-a, a) << "\n";
					// cout << t.substr(j, a) << "\n";
				}
				if(s.substr(i-a, a) == t.substr(j, a))
					b_a = a;
			}
			for(int b = 1; i + b <= s.size() && j - b >= 0; b++) {
				if(s.substr(i, b) == t.substr(j - b, b))
					b_b = b;
			}

			// if(b_a != 0 && b_b != 0) cout << b_a << " " << b_b << ": " << b_a + b_b << "\n";
			if(b_a + b_b > maximo) {
				maximo = b_a + b_b;
				ini = i - b_a;
				fim = t.size() - (j + b_a);
			}
		}
	}
	cout << maximo << "\n" << ini << " " << fim << "\n";
	return 0;
}

Compilation message

necklace.cpp: In function 'int main()':
necklace.cpp:13:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < s.size(); i++) {
                 ~~^~~~~~~~~~
necklace.cpp:14:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < t.size(); j++) { 
                  ~~^~~~~~~~~~
necklace.cpp:20:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int a = 1; i - a >= 0 && j + a <= t.size(); a++) {
                                 ~~~~~~^~~~~~~~~~~
necklace.cpp:29:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int b = 1; i + b <= s.size() && j - b >= 0; b++) {
                   ~~~~~~^~~~~~~~~~~
necklace.cpp:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < s.size(); i++) {
                 ~~^~~~~~~~~~
necklace.cpp:44:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < t.size(); j++) { 
                  ~~^~~~~~~~~~
necklace.cpp:50:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int a = 1; i - a >= 0 && j + a <= t.size(); a++) {
                                 ~~~~~~^~~~~~~~~~~
necklace.cpp:59:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int b = 1; i + b <= s.size() && j - b >= 0; b++) {
                   ~~~~~~^~~~~~~~~~~
necklace.cpp:72:49: warning: 'fim' may be used uninitialized in this function [-Wmaybe-uninitialized]
  cout << maximo << "\n" << ini << " " << fim << "\n";
                                                 ^~~~
necklace.cpp:72:35: warning: 'ini' may be used uninitialized in this function [-Wmaybe-uninitialized]
  cout << maximo << "\n" << ini << " " << fim << "\n";
                                   ^~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 256 KB Output is correct
2 Correct 117 ms 384 KB Output is correct
3 Correct 75 ms 256 KB Output is correct
4 Correct 84 ms 376 KB Output is correct
5 Correct 103 ms 256 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 256 KB Output is correct
2 Correct 117 ms 384 KB Output is correct
3 Correct 75 ms 256 KB Output is correct
4 Correct 84 ms 376 KB Output is correct
5 Correct 103 ms 256 KB Output is correct
6 Execution timed out 1556 ms 376 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 256 KB Output is correct
2 Correct 117 ms 384 KB Output is correct
3 Correct 75 ms 256 KB Output is correct
4 Correct 84 ms 376 KB Output is correct
5 Correct 103 ms 256 KB Output is correct
6 Execution timed out 1556 ms 376 KB Time limit exceeded
7 Halted 0 ms 0 KB -