CSES - E4590 2020 2 - Results
Submission details
Task:Swapping letters
Sender:kkivimaki
Submission time:2020-09-19 16:12:42 +0300
Language:C++ (C++11)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.01 sdetails
#2ACCEPTED0.01 sdetails
#3ACCEPTED0.01 sdetails
#40.11 sdetails
#50.09 sdetails
#60.75 sdetails
#7ACCEPTED0.05 sdetails
#80.08 sdetails
#90.08 sdetails
#100.08 sdetails

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:35:14: warning: array subscript has type 'char' [-Wchar-subscripts]
         l0[c0].push_back(c1);
              ^
input/code.cpp:36:14: warning: array subscript has type 'char' [-Wchar-subscripts]
         l0[c1].push_back(c0);
              ^
input/code.cpp:56:29: warning: array subscript has type 'char' [-Wchar-subscripts]
         int j = find(y, at[c], c);
                             ^
input/code.cpp:57:13: warning: array subscript has type 'char' [-Wchar-subscripts]
         at[c] = j + 1;
             ^
input/code.cpp:59:26: warning: array subscript has type 'char' [-Wchar-subscripts]
         for (int r : l0[c]) {
                          ^
input/code.cpp:64:26: warning: array subscript has type 'char' [-Wchar-subscripts]
             for(a = pvy[c][r]; y[a] != c; a++)
                          ^
input/code.cpp:67:18: warning: array subscript has type 'char' [-Wchar-subscripts]
             pvy[c][r] = a + 1;...

Code

#include <vector>
#include <iostream>
#include <string>
std::vector<int> l0[1000];
int at[123];
int prx[123];
int pry[123][123];
int pvy[123][123];
int find(const char* y, int a, char c) {
int i = a;
while(y[i] != c) i++;
return i;
}
int main() {
for(int i = 0; i < 123; i++) {
for(int j = 0; j < 123; j++) {
pvy[i][j] = 0;
pry[i][j] = 0;
}
}
int n;
std::cin >> n;
while (n > 0) {
n -= 1;
char c0;
char c1;
std::cin >> c0;
std::cin >> c1;
l0[c0].push_back(c1);
l0[c1].push_back(c0);
}
std::string x0;
std::string y0;
std::cin >> x0;
std::cin >> y0;
int N = x0.size();
const char* x = x0.c_str();
const char* y = y0.c_str();
int i = 0;
for(int i = 0; i < N; i++) {
if (i % 10000 == 9999)
std::cout << i << " " << N << std::endl;
char c = x[i];
int j = find(y, at[c], c);
at[c] = j + 1;
for (int r : l0[c]) {
int cx = prx[r];
int n = 0;
int a;
for(a = pvy[c][r]; y[a] != c; a++)
if (y[a] == r) n++;
pvy[c][r] = a + 1;
pry[c][r] += n;
int cy = pry[c][r];
if (cx != cy) {
std::cout << "NO" << std::endl;
return 0;
}
}
prx[c] += 1;
}
std::cout << "YES" << std::endl;
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:

input
10
d c
e b
f y
h q
...

correct output
YES

user output
9999 1000000
19999 1000000
29999 1000000
39999 1000000
49999 1000000
...
Truncated

Test 5

Verdict:

input
10
a i
a l
d a
g h
...

correct output
NO

user output
9999 1000000
19999 1000000
29999 1000000
39999 1000000
49999 1000000
...
Truncated

Test 6

Verdict:

input
325
a b
a e
a f
a g
...

correct output
YES

user output
9999 1000000
19999 1000000
29999 1000000
39999 1000000
49999 1000000
...
Truncated

Test 7

Verdict: ACCEPTED

input
325
a c
a e
a g
a h
...

correct output
NO

user output
NO

Test 8

Verdict:

input
0
dlkinfmdyjaofxbccwhhbxzartqwdr...

correct output
YES

user output
9999 1000000
19999 1000000
29999 1000000
39999 1000000
49999 1000000
...
Truncated

Test 9

Verdict:

input
0
bxisdrdpgcsnnvhnfgimivzqpqjwqc...

correct output
NO

user output
9999 1000000
19999 1000000
29999 1000000
39999 1000000
49999 1000000
...
Truncated

Test 10

Verdict:

input
0
mrwduerojcguvxzmbomfsainvqehsl...

correct output
NO

user output
9999 1000000
19999 1000000
29999 1000000
39999 1000000
49999 1000000
...
Truncated