Submission details
Task:Swapping letters
Sender:Pohjantahti
Submission time:2018-09-17 19:13:47 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.02 sdetails
#2ACCEPTED0.01 sdetails
#3ACCEPTED0.01 sdetails
#4ACCEPTED0.13 sdetails
#5ACCEPTED0.11 sdetails
#6ACCEPTED0.64 sdetails
#7ACCEPTED0.41 sdetails
#8ACCEPTED0.10 sdetails
#9ACCEPTED0.01 sdetails
#10ACCEPTED0.03 sdetails

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