Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Fix just one travel direction first. Peter was awake twice, so in that direction his notes must correspond to two contiguous substrings of the route string, appearing in chronological order.
Be careful with the note: one flag cannot be seen twice. So if the first note starts at position and has length , then the second one must start at some with Overlap is illegal.
For one direction, do you really need to try every occurrence of the first string? Suppose some occurrence works. Would using an even earlier occurrence of the same first string ever make the second string harder to place?
Let be the leftmost occurrence of the first note. If some valid solution uses the first note at , then , so Therefore the same second occurrence is still to the right of the leftmost first occurrence. So for one direction, it is enough to:
Write a helper check(s, a, b):
a in s;false;b starting from index pos_a + |a|.
Run this on the original string for forward, and on reverse(s) for backward. Since , even a dumb substring search is totally fine. Nice and boring — the good kind.Don't overthink the train story. In one fixed direction, Peter's two wakeful periods mean:
So for a route string , we need to know whether there exist indices such that
That last condition is the whole game: the blocks must not overlap, because one station cannot be seen twice. That's the sneaky little trap.
A brute-force mindset says: try every occurrence of , then see whether appears later. That works, but there's an even cleaner observation.
Let be the leftmost occurrence of in . Assume some valid solution exists with starting at and starting at . Then clearly , hence
So the very same occurrence of at position is also after the end of the leftmost occurrence of .
That means:
If a solution exists at all, then using the first occurrence of also works.
So for one direction, the check is simply:
No DP. No suffix automaton. No dark arts. Just two substring searches and a bit of honesty.
The route from to is exactly the reverse of the route from to . So let
Then Peter could have seen the same two notes on the return trip iff the same condition holds in :
Important: reverse only the route string, not or . Peter wrote the colors in the order he saw them, so on the backward trip we compare against the reversed station order directly.
Define check(s, a, b):
false;Then:
forward = check(s, a, b)backward = check(reverse(s), a, b)Finally print:
both if both are true;forward if only forward is true;backward if only backward is true;fantasy otherwise.A naive substring finder is more than enough here because
Each search costs at worst , so one direction is
and both directions are still just
With these limits, that's comfortably fast.
If and overlap as strings inside , that still does not mean the answer is valid. The second one must start at or after the end of the first one:
That's the kind of bug that gets you a Wrong Answer and a mild identity crisis. Avoid it.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int findSub(const string& s, const string& t, int start) {
int n = (int)s.size();
int m = (int)t.size();
for (int i = start; i + m <= n; ++i) {
bool ok = true;
for (int j = 0; j < m; ++j) {
if (s[i + j] != t[j]) {
ok = false;
break;
}
}
if (ok) return i;
}
return -1;
}
bool check(const string& s, const string& a, const string& b) {
int p = findSub(s, a, 0);
if (p == -1) return false;
int q = findSub(s, b, p + (int)a.size());
return q != -1;
}
int main() {
setIO();
string s, a, b;
cin >> s >> a >> b;
bool forward = check(s, a, b);
reverse(s.begin(), s.end());
bool backward = check(s, a, b);
if (forward && backward) cout << "both\n";
else if (forward) cout << "forward\n";
else if (backward) cout << "backward\n";
else cout << "fantasy\n";
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int findSub(const string& s, const string& t, int start) {
int n = (int)s.size();
int m = (int)t.size();
for (int i = start; i + m <= n; ++i) {
bool ok = true;
for (int j = 0; j < m; ++j) {
if (s[i + j] != t[j]) {
ok = false;
break;
}
}
if (ok) return i;
}
return -1;
}
bool check(const string& s, const string& a, const string& b) {
int p = findSub(s, a, 0);
if (p == -1) return false;
int q = findSub(s, b, p + (int)a.size());
return q != -1;
}
int main() {
setIO();
string s, a, b;
cin >> s >> a >> b;
bool forward = check(s, a, b);
reverse(s.begin(), s.end());
bool backward = check(s, a, b);
if (forward && backward) cout << "both\n";
else if (forward) cout << "forward\n";
else if (backward) cout << "backward\n";
else cout << "fantasy\n";
}