| 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 |
