Task: | Swapping letters |
Sender: | Pohjantahti |
Submission time: | 2018-09-15 15:59:49 +0300 |
Language: | C++ |
Status: | READY |
Result: | WRONG ANSWER |
test | verdict | time | |
---|---|---|---|
#1 | WRONG ANSWER | 0.03 s | details |
#2 | ACCEPTED | 0.01 s | details |
#3 | ACCEPTED | 0.03 s | details |
#4 | WRONG ANSWER | 0.21 s | details |
#5 | ACCEPTED | 0.23 s | details |
#6 | ACCEPTED | 0.74 s | details |
#7 | WRONG ANSWER | 0.73 s | details |
#8 | ACCEPTED | 0.22 s | details |
#9 | ACCEPTED | 0.02 s | details |
#10 | ACCEPTED | 0.03 s | details |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:79:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int i = 0; i < pos[0][c].size(); ++i) { ~~^~~~~~~~~~~~~~~~~~ input/code.cpp:84:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] if (x+h < pos[1][d].size() && pos[1][d][x+h] < st) x += h; ~~~~^~~~~~~~~~~~~~~~~~ input/code.cpp:87:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] if (x < pos[1][d].size()) { ~~^~~~~~~~~~~~~~~~~~ input/code.cpp:81:9: warning: unused variable 'ed' [-Wunused-variable] int ed = pos[1][c][i]; ^~
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 int cnt[30][1000005]; void fail() { cout << "NO\n"; exit(0); } int count(int ch, int l, int r) { if (l > r) swap(l, r); int cres = cnt[ch][r]; if (l > 0) { cres -= cnt[ch][l-1]; } return cres; } 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 i = 0; i < n; ++i) { if (i > 0) { cnt[c][i] += cnt[c][i-1]; } if ((a[i]-'a') == c) { cnt[c][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]; int x = -1; for (int h = (1<<21); h >= 1; h /= 2) { if (x+h < pos[1][d].size() && pos[1][d][x+h] < st) x += h; } x++; if (x < pos[1][d].size()) { if ((pos[0][d][x] < st && pos[1][d][x] > st)) { fail(); } } } } /* for (int i = 0; i < pos[0][c].size(); ++i) { int sr = pos[0][c][i]; int de = pos[1][c][i]; if (sr == de) { continue; } for (int ic = 0; ic < 26; ++ic) { if (ic == c) continue; if (ig[c][ic]) { if (count(ic, sr, de) > 0) { if (sr < de) { } } } } }*/ } cout << "YES\n"; return 0; }
Test details
Test 1
Verdict: WRONG ANSWER
input |
---|
5 a b b c c d d e ... |
correct output |
---|
YES |
user output |
---|
NO |
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: WRONG ANSWER
input |
---|
10 d c e b f y h q ... |
correct output |
---|
YES |
user output |
---|
NO |
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: WRONG ANSWER
input |
---|
325 a c a e a g a h ... |
correct output |
---|
NO |
user output |
---|
YES |
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 |