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