QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#704142 | #162. Merges and Acquisitions | TheZone | AC ✓ | 1ms | 3880kb | C++20 | 3.6kb | 2024-11-02 19:23:59 | 2024-11-02 19:24:00 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef int int2;
#define int long long
#define pi pair<int, int>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define f first
#define s second
const int inf = 1e18;
int t;
const int maxn = 1e5 + 5;
vector<int> divs[maxn];
int dp[maxn];
#define EPS 1e-4
void gg() {
cout << "NO\n";
exit(0);
}
typedef double D;
D dis(D a, D b, D c, D d) {
D dx = c - a;
D dy = d - b;
return sqrt(dx * dx + dy * dy);
}
bool check(string A, string B, string S) {
int n = S.size();
int ia = 0;
int ib = 0;
bool possible = true;
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
while (ia < (int)A.size() and A[ia] != S[i]) {
ia++;
}
if (ia == (int)A.size()) possible = false;
ia++;
} else {
while (ib < (int)B.size() and B[ib] != S[i]) {
ib++;
}
if (ib == (int)B.size()) possible = false;
ib++;
}
}
return possible;
}
int2 main() {
ios::sync_with_stdio(0);
cin.tie(0);
string S, T;
cin >> S >> T;
string target = S;
if (check(S, T, target) or check(T, S, target)) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
/*#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second
const int MAXV = 10000000;
int val[MAXV], stepp[MAXV];
int dist[MAXV];
const int MAXV2 = 30010;
vector<int> g_lol[MAXV2];
void solve() {
int n, m; cin >> n >> m;
int curv = n;
map<pair<int, int>, int> pos;
int p0, p1;
for (int i = 0; i < m; i++) {
int b, g; cin >> b >> g;
if (i == 0) p0 = b;
if (i == 1) p1 = b;
if (pos.find({b % g, g}) != pos.end()) {
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
continue;
}
pos[{b % g, g}] = curv;
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
for (int j = b % g; j < n; j += g) {
val[curv] = j;
stepp[curv] = g;
curv++;
}
}
for (int i = 0; i < curv; i++) dist[i] = 1e9;
dist[p0] = 0;
deque<int> q;
q.push_back(p0);
while (!q.empty()) {
int v = q.front();
q.pop_front();
if (v < n) {
for (int el : g_lol[v]) {
if (dist[el] > dist[v]) {
dist[el] = dist[v];
q.push_front(el);
}
}
} else {
if (val[v] - stepp[v] >= 0 && dist[v - 1] > dist[v] + 1) {
dist[v - 1] = dist[v] + 1;
q.push_back(v - 1);
}
if (val[v] + stepp[v] < n && dist[v + 1] > dist[v] + 1) {
dist[v + 1] = dist[v] + 1;
q.push_back(v + 1);
}
if (dist[val[v]] > dist[v]) {
dist[val[v]] = dist[v];
q.push_front(val[v]);
}
}
}
cout << (dist[p1] == 1e9 ? -1 : dist[p1]) << '\n';
}
signed main() {
int tt = 1;
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cin >> tt;
#else
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#endif
while (tt--) {
solve();
}
return 0;
}*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3624kb
input:
acmicpc tsukuba
output:
No
result:
ok single line: 'No'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3816kb
input:
hoge moen
output:
Yes
result:
ok single line: 'Yes'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
abcdefg xacxegx
output:
Yes
result:
ok single line: 'Yes'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
bbaaabba bababaaa
output:
Yes
result:
ok single line: 'Yes'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
abbbabbbaaaabaabbaaab babaaabbbababbbbbbbba
output:
No
result:
ok single line: 'No'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3524kb
input:
aaaab abccb
output:
No
result:
ok single line: 'No'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
cbcbcaccbabaabaab bbbbbaaabcbabcacc
output:
No
result:
ok single line: 'No'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
cbabdbdbdbaabcc bccabcabcaabdcd
output:
No
result:
ok single line: 'No'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3808kb
input:
bbacbacbacbb bbbcacdddcdd
output:
No
result:
ok single line: 'No'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
ccbedcdceeddbbebbcbeeddd ecdceeedeeadaacdacddaabb
output:
No
result:
ok single line: 'No'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3612kb
input:
bccbebbbebdcdaebb bacdacddaebdcacad
output:
No
result:
ok single line: 'No'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3872kb
input:
abfcedbacefaafc bccabfacbbbffcf
output:
No
result:
ok single line: 'No'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3876kb
input:
d d
output:
Yes
result:
ok single line: 'Yes'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3608kb
input:
cbegeccgfedcag addgbggaacbbdg
output:
No
result:
ok single line: 'No'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
ebefgdcgecadecffbccdeg fccggegafdecfegffdaefc
output:
No
result:
ok single line: 'No'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
dcd heh
output:
No
result:
ok single line: 'No'
Test #17:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
agddff cdfbbd
output:
No
result:
ok single line: 'No'
Test #18:
score: 0
Accepted
time: 1ms
memory: 3580kb
input:
ehbbfdieaie dchigebgiea
output:
No
result:
ok single line: 'No'
Test #19:
score: 0
Accepted
time: 1ms
memory: 3868kb
input:
dbfahbhdgcifcihaabghcfica ddhbcddgeedfgaihadecaddcb
output:
No
result:
ok single line: 'No'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3680kb
input:
cbfhhceadcdiahiighihbaebefegh dacdhhgjijjbdhjgggigbgbcjiabd
output:
No
result:
ok single line: 'No'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3808kb
input:
fbaiejbcia ggfefdifcg
output:
No
result:
ok single line: 'No'
Test #22:
score: 0
Accepted
time: 1ms
memory: 3612kb
input:
ibeifkbggcffahcabcgikfccad kkkiaackbcgcjddigkkcgkjkfd
output:
No
result:
ok single line: 'No'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
fgfdhf agibke
output:
No
result:
ok single line: 'No'
Test #24:
score: 0
Accepted
time: 1ms
memory: 3880kb
input:
bbbbbaabbabbaabbabbbbaaabbbbbbaabaabaaabbabbababaaaababaabbbaaababbbbaaabbbbbaabaabbaaaababbbaaaababbaaabbbbbbbababbaabbaababbbaaaaabbbbaaaabaabaabaaaaaabbaabaabbaabbaabaabaababbbabbaaaaabababbbbbaaaabbbbaabaabbbababbbbbabaababaabaaaabbbbabaabbbabbababbabbaabaaabbaabababbaabaabaababbbabbabbbabbbbbab...
output:
No
result:
ok single line: 'No'
Test #25:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
bbbabbbaaabaabaabbabbabaababbbaaabbbbaabababbaabbbaaaabbabababbbbbbaabaaababbaaaaabbbaaabbaabbbbbbabbaabaabbaaabababbabaaaaaabaaaababbbaabbabbaaaabbaaababbababbaabaaabbbaabbbaabbabaaaaababaabaabaaaabbbabaaaaaaabababaaaaabbababbaababbabaabaabaaabaaaabbaaabaababbaaaabbbbbbbbbbbabbbbbbbabbbbaabaaabaabb...
output:
Yes
result:
ok single line: 'Yes'
Test #26:
score: 0
Accepted
time: 1ms
memory: 3880kb
input:
abaababbabbbabbaaaaabbaabbbbaabbbabbaaaaaabaaaaaabaabbbbaaaaaabbabbaaaaaabbabaabbbaababaaababbabbbabbabaaaababbaabaababaaabaaabbaaababaabbbbbaabbababbabbababbbbaababaaaaababababbaaaaabbaaabbaabbaaabbbaaabaaabaaabbbbbbbbabaaabbbbaabbbbaabbbbaababbbbbbabaaababbaaaabbbbbabbbbabbababbaaabbbaaababaaabbaa...
output:
Yes
result:
ok single line: 'Yes'
Test #27:
score: 0
Accepted
time: 1ms
memory: 3812kb
input:
aaaabbaabababababbabbaabbbbaabbbbaaabbbaababbaabaabaaababaabbbaaabaaaaabbaaabababbbbababbabaaaaaabbbababbbbbbbbbbbaaabaabbabaabbabbaaaaabbaaabbabbaaabbbabbbaabaabaabbaababaabbbbaabbbbabaaabbbbaaabaababaabbaaaabbababaabbbbbbbabbababbaabbbaaababbbbbaabbbbbaaabaaabaaabbaabbaababbbababbaaabababaabbabbaa...
output:
Yes
result:
ok single line: 'Yes'
Test #28:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
bbbbabbaabbaababbabbabbbbbabbaaabbbbabbaabaaababbbabbbaabaabbbbbaababaabbaaababbababbaaaabaaabbabbbaabaaaabbababaababbbabaaaabaabbababaaaaababaaabbababababababaabaabbabbbbbbaaabbaabbababbababaabaaaaababbbabbbababababbaabbaaababbaaaaaaabaababbbbaaabababbaaabbbbbbbbabaabbabbbbaaaaaaabbababaababbbabbbb...
output:
Yes
result:
ok single line: 'Yes'
Test #29:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
abaaaabbbbbbaabbabbbbbabbabbaaaabaaaabaaaaaaaabbbbabaabaaabbaabbbabababaaabaabbabbbabbbabbaaabbbabaaaaabababbbbbbbaabbabaabaabbabaaaabbbbbabaabaaaabaabbaabbbbaabaabbabbababaabaabbbbaaaaaaabbbaabaabaababbbbababbbabbbabaaabbabbaaaaaabbababbbabaaaabaabaaabbbaababaaababababaabbabbaabbbbababbbaaabbbbbaaa...
output:
Yes
result:
ok single line: 'Yes'
Test #30:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
bbaaaabaababaabbababaabbbabbaaaaaaabaabbabbabaaaaaaaabaaaabbbaaaaabaaaabbbbbbabaabbbaabbbbbababbaaabaababaabbabbababaaabaaaabaabaabbabbababbbaaabaaaabbaaaaaaaabaaabaabaababaaabbaababaababbaababbabbbbbbaababaaabbababaaababbababbaaabababbbaaabbabbabbaabaababbbbabababababbbaabaababbabaaabaaaabbaababbab...
output:
Yes
result:
ok single line: 'Yes'
Test #31:
score: 0
Accepted
time: 1ms
memory: 3580kb
input:
abbababbababaaababbabbbaabbabbbbababaabaabbaaaaabaaabaabbabbbbbbababbabaaaaaabaaabbbbbabbbabaabbaabbabaabbabaabbbbaaaaaaaaabbabbaaabbbababaaaaabbabaaabbabbabaabbbbaababaaababbaababbbbbbabaaabbbabbbbbbbabaaababbbbaaababbaababbbaaaabbababaabbabbbabbbabaaaaabbbbabababaabbababaaaabbabbabbaabaabbabbbbaaa...
output:
Yes
result:
ok single line: 'Yes'
Test #32:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
aabaaabaabaababaababbabaaaababbbaabbabbabaaabababaaabaaaaaaaaaabbabaabbbaaababbaaaabaaababbabaaaabababbbaaaaaaabbbaaaaabababaabaaaabbbababbbbbabbababbbbbaabaaabbabbaabaaabbabbababaabaabaabbbabbbabbbaaabbbabbababbbabbabbbaaababaabbabaabbaaaaabbaaabbbaaabbaaaaaaaabbaabaababaabbabbbaabbbaaaaaababbaaaba...
output:
Yes
result:
ok single line: 'Yes'
Test #33:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
baaaabbababaabaabababbbaaaaabaabbbabbaaaabababbabbbbaaaaabbbbababbbababaabbbabbbabaaaaabbbbbabbbbabbbabbbaaaabbaabbbaaaaabbbbababbbabbbbaaabbbaaaababaabaabaaababbbbabbabbaaaaaaaaaabaababbabbabbbbbbbbbbabbaabaaabaabaaaababbabaabaaabbbbbaabbaaaaababbbababaaabbbbaaabaaabaabaaabaabaaaaaaaaabaaabbabaabab...
output:
Yes
result:
ok single line: 'Yes'
Test #34:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
bbbabbbbabaabbabbbbbbbabaaabbabbbbabbabbbaabaaabbabbaabbaaaaaaabaabbbbaabbaabaaabbbabaaabbbabbaaaabbbababaabaaabbbbabaaabaabbaaabbabaabaabbaaabaababbaabaaababaababbaaaaabaaabaaaabbaabaabaabaaabbaabbaabbaaabbbbbbbaababaabbbabababaaaaabbaabbbbbaaabaabbbbbabbaaaabbabaabbbabaaaaaabbbaaababbabbababbababb...
output:
No
result:
ok single line: 'No'
Test #35:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
wbcdugsigbadgwdjcnznraospkxxjtkbratqjyupbkhzsccsfpmmlzjfwzybbwlwlzxzftnfjnzjkuuypxbzizfbjwfpriboezxebcrqkufavpvuitlwzrriqyuijtyggvqrrrugybqgrkmymqsohyugnrunqqwmcmxljvcyrmqxvjxixlfvjvffqtwqnubytbafwrxipedrjjqzxdwdgmfltisbghorrcoguarlsqqvhnptgwaapiatqqumjtygqnmhmuyezlpawpzkkzecjspopwsbczuwjtoalvvvbovh...
output:
No
result:
ok single line: 'No'
Test #36:
score: 0
Accepted
time: 1ms
memory: 3880kb
input:
ababbabbbabbbbaaabbabababbaaabbababbaabbaaababbbbaaabababbbbaabbbbabababbbabababbbbaaaaaaaaaabaabaabbabaaabaaaaabbbbabaaabaabbbbbabaaaabaaaaabaabbbabaabaaaaabbbbbbababbaabbabaaaaabababbbababbaaabbbbababbabbabbabaabbaabbbaabbbaabaababbaabbbabbababaaaabaabaabbaaabababaaabbaaaaabbaabababbbaabbbabbaabba...
output:
No
result:
ok single line: 'No'
Test #37:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
abbaaaabbbaaaaaabbbbaaaaaabbbbbbabbaaaaaabbabaaabbaaaabbaaaabbabbabaaaaaaabaaaababbbabaaaababaaaaabbaaaabaaaababbaabbabbbaabaabbabbbabbaaabababbaababaaaabbabbaabbaabbbaaaaaabaabaaabbabaaabaaaabaababbbaaaababbabbaabbaabababbbbbaaaabbabaaaaababbbbbabbbaaaaabbaaaabbbbbbaabbbbaaaabbaabbbbabbaaabbabbbaaa...
output:
Yes
result:
ok single line: 'Yes'
Test #38:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
aaaaaaabbbbababbbaaaababaababbaaababbabbbabaaaabbababbaababbbbabbbaabbababaaaaaaaaababaabbbbaabaabbbaabaaabababbbaabaabbaabababababbbbbabbaabbbabbaababbbbaaababbbbbaaabaabaabaabaaabaabbaaaaaabbbabaaababaabbabaaaaaaaaaaababbbababbbaababbbbbaabbaaabbaaaaaababaababaabbababbbabbbabbabaaababbaaaaabaababb...
output:
Yes
result:
ok single line: 'Yes'
Test #39:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
bbabbbbababbbbbabaabaaababbabbbbbbbbaaababbaabaaabbabbabbaaaaaabbaaaaabaabbababbbbbabababbbbbbbabbababaababbaaaabaaabababbaaababbbabababababaabaaababababaabaabbaaaabaababbababbbaabbbababaababbabaaabbaabaababaabaaaababbaaaaabaaabbabbaaaaabaaabbabaaabaababaaaaababbbabaaabbbaaaabbbbbbbabbababbaabaabaaa...
output:
Yes
result:
ok single line: 'Yes'
Test #40:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
stststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststst...
output:
Yes
result:
ok single line: 'Yes'
Test #41:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...
output:
Yes
result:
ok single line: 'Yes'
Test #42:
score: 0
Accepted
time: 1ms
memory: 3676kb
input:
tstststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststststs...
output:
Yes
result:
ok single line: 'Yes'
Test #43:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss tststststststststststststststststststststststststststststststststststststststststststststststststststststs...
output:
Yes
result:
ok single line: 'Yes'
Test #44:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...
output:
Yes
result:
ok single line: 'Yes'
Test #45:
score: 0
Accepted
time: 1ms
memory: 3676kb
input:
m a
output:
Yes
result:
ok single line: 'Yes'
Test #46:
score: 0
Accepted
time: 1ms
memory: 3608kb
input:
abab aaaa
output:
Yes
result:
ok single line: 'Yes'
Test #47:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
abab bbbb
output:
Yes
result:
ok single line: 'Yes'