oj.uz

Submission #538045

# Submission time Handle Problem Language Result Execution time Memory
538045 2022-03-16T04:01:15 Z skittles1412 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
25 / 85
 1500 ms 304 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

bool eqr(string s, const string &t) {
	for (int i = 0; i < sz(s); i++) {
		if (s == t) {
			return true;
		}
		rotate(s.begin(), s.begin() + 1, s.end());
	}
	return false;
}

bool eq(string s, const string &t) {
	if (eqr(s, t)) {
		return true;
	}
	reverse(begin(s), end(s));
	return eqr(s, t);
}

void solve() {
	dbg(eq("a", "b"));
	string s, t;
	cin >> s >> t;
	int n = sz(s), m = sz(t);
	for (int i = n; i >= 1; i--) {
		for (int j = 0; j + i <= n; j++) {
			for (int k = 0; k + i <= m; k++) {
				if (eq(s.substr(j, i), t.substr(k, i))) {
					cout << i << endl;
					cout << j << " " << k << endl;
					return;
				}
			}
		}
	}
	assert(false);
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cin.exceptions(ios::failbit);
	solve();
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 212 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 89 ms 304 KB Output is correct
4 Correct 135 ms 300 KB Output is correct
5 Correct 287 ms 296 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 212 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 89 ms 304 KB Output is correct
4 Correct 135 ms 300 KB Output is correct
5 Correct 287 ms 296 KB Output is correct
6 Correct 803 ms 300 KB Output is correct
7 Execution timed out 1585 ms 304 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 212 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 89 ms 304 KB Output is correct
4 Correct 135 ms 300 KB Output is correct
5 Correct 287 ms 296 KB Output is correct
6 Correct 803 ms 300 KB Output is correct
7 Execution timed out 1585 ms 304 KB Time limit exceeded
8 Halted 0 ms 0 KB -