Submission details
Task:Swapping letters
Sender:Pohjantahti
Submission time:2018-09-15 15:59:49 +0300
Language:C++
Status:READY
Result:
Test results
testverdicttime
#10.03 sdetails
#2ACCEPTED0.01 sdetails
#3ACCEPTED0.03 sdetails
#40.21 sdetails
#5ACCEPTED0.23 sdetails
#6ACCEPTED0.74 sdetails
#70.73 sdetails
#8ACCEPTED0.22 sdetails
#9ACCEPTED0.02 sdetails
#10ACCEPTED0.03 sdetails

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:

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:

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:

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