Task: | Swapping letters |
Sender: | Pohjantahti |
Submission time: | 2018-09-17 19:13:47 +0300 |
Language: | C++ |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.02 s | details |
#2 | ACCEPTED | 0.01 s | details |
#3 | ACCEPTED | 0.01 s | details |
#4 | ACCEPTED | 0.13 s | details |
#5 | ACCEPTED | 0.11 s | details |
#6 | ACCEPTED | 0.64 s | details |
#7 | ACCEPTED | 0.41 s | details |
#8 | ACCEPTED | 0.10 s | details |
#9 | ACCEPTED | 0.01 s | details |
#10 | ACCEPTED | 0.03 s | details |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:58:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int i = 0; i < pos[0][c].size(); ++i) { ~~^~~~~~~~~~~~~~~~~~ input/code.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] if (x+h < pos[0][d].size() && pos[0][d][x+h] < st) x += h; ~~~~^~~~~~~~~~~~~~~~~~ input/code.cpp:67:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] if (x == pos[0][d].size()) { ~~^~~~~~~~~~~~~~~~~~~ input/code.cpp:86:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] if (x+h < pos[1][d].size() && pos[1][d][x+h] < ed) x += h; ~~~~^~~~~~~~~~~~~~~~~~ input/code.cpp:89:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] if (x == pos[1][d].size()) { ~~^~~~~~~~~~~~~~~~~~~...
Code
#pragma GCC optimize("O3") #pragma GCC target("arch=skylake") #include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; int pc; int n, m; string a, b; bool ig[30][30]; vector<int> pos[2][30]; // 0 src, 1 dest void fail() { cout << "NO\n"; exit(0); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> pc; for (int i = 0; i < pc; ++i) { char u, v; cin >> u >> v; int sr = u-'a'; int de = v-'a'; ig[sr][de] = ig[de][sr] = true; } cin >> a >> b; n = a.length(); m = b.length(); if (n != m) { fail(); } string ta = a; string tb = b; sort(ta.begin(), ta.end()); sort(tb.begin(), tb.end()); if (ta != tb) { fail(); } for (int i = 0; i < n; ++i) { int cc = a[i]-'a'; pos[0][cc].push_back(i); } for (int i = 0; i < m; ++i) { int cc = b[i]-'a'; pos[1][cc].push_back(i); } for (int c = 0; c < 26; ++c) { for (int d = c+1; d < 26; ++d) { if (!ig[c][d]) continue; for (int i = 0; i < pos[0][c].size(); ++i) { int st = pos[0][c][i]; int ed = pos[1][c][i]; if (st <= ed) { int x = -1; for (int h = (1<<21); h >= 1; h /= 2) { if (x+h < pos[0][d].size() && pos[0][d][x+h] < st) x += h; } x++; if (x == pos[0][d].size()) { continue; } int rst = pos[0][d][x]; int red = pos[1][d][x]; if (rst <= red) { if (st <= rst && red <= ed) { fail(); } } else { if (st <= rst && rst <= ed) { fail(); } } } else { int x = -1; for (int h = (1<<21); h >= 1; h /= 2) { if (x+h < pos[1][d].size() && pos[1][d][x+h] < ed) x += h; } x++; if (x == pos[1][d].size()) { continue; } int red = pos[1][d][x]; int rst = pos[0][d][x]; if (red <= rst) { if (ed <= red && rst <= st) { fail(); } } else { if (ed <= red && red <= st) { fail(); } } } } } } cout << "YES\n"; return 0; }
Test details
Test 1
Verdict: ACCEPTED
input |
---|
5 a b b c c d d e ... |
correct output |
---|
YES |
user output |
---|
YES |
Test 2
Verdict: ACCEPTED
input |
---|
2 a b b c acbbaca cabbaac |
correct output |
---|
YES |
user output |
---|
YES |
Test 3
Verdict: ACCEPTED
input |
---|
2 a b b c acbbaca baccaab |
correct output |
---|
NO |
user output |
---|
NO |
Test 4
Verdict: ACCEPTED
input |
---|
10 d c e b f y h q ... |
correct output |
---|
YES |
user output |
---|
YES |
Test 5
Verdict: ACCEPTED
input |
---|
10 a i a l d a g h ... |
correct output |
---|
NO |
user output |
---|
NO |
Test 6
Verdict: ACCEPTED
input |
---|
325 a b a e a f a g ... |
correct output |
---|
YES |
user output |
---|
YES |
Test 7
Verdict: ACCEPTED
input |
---|
325 a c a e a g a h ... |
correct output |
---|
NO |
user output |
---|
NO |
Test 8
Verdict: ACCEPTED
input |
---|
0 dlkinfmdyjaofxbccwhhbxzartqwdr... |
correct output |
---|
YES |
user output |
---|
YES |
Test 9
Verdict: ACCEPTED
input |
---|
0 bxisdrdpgcsnnvhnfgimivzqpqjwqc... |
correct output |
---|
NO |
user output |
---|
NO |
Test 10
Verdict: ACCEPTED
input |
---|
0 mrwduerojcguvxzmbomfsainvqehsl... |
correct output |
---|
NO |
user output |
---|
NO |