| Task: | Alien Invasion II |
| Sender: | kkivimaki |
| Submission time: | 2020-09-19 16:17:49 +0300 |
| Language: | C++ (C++11) |
| Status: | READY |
| Result: | TIME LIMIT EXCEEDED |
| test | verdict | time | |
|---|---|---|---|
| #1 | TIME LIMIT EXCEEDED | -- | details |
| #2 | TIME LIMIT EXCEEDED | -- | details |
| #3 | TIME LIMIT EXCEEDED | -- | details |
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:53:29: warning: array subscript has type 'char' [-Wchar-subscripts]
int j = find(y, at[c], c);
^
input/code.cpp:54:13: warning: array subscript has type 'char' [-Wchar-subscripts]
at[c] = j + 1;
^
input/code.cpp:56:26: warning: array subscript has type 'char' [-Wchar-subscripts]
for (int r : l0[c]) {
^
input/code.cpp:61:26: warning: array subscript has type 'char' [-Wchar-subscripts]
for(a = pvy[c][r]; y[a] != c; a++)
^
input/code.cpp:64: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++) {
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;
}
for(int c = 97; c <= 122; c++) {
int n = 0;
int m = 0;
for(int i = 0; i < N; i++) {
n += x[i] == c;
m += y[i] == c;
}
if (n != m) {
std::cout << "NO" << std::endl;
return 0;
}
}
std::cout << "YES" << std::endl;
return 0;
}
Test details
Test 1
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 2368469234876449 |
| correct output |
|---|
| 22368469234876449 3 7456156411625483 |
| user output |
|---|
| (empty) |
Test 2
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 292929292929292929292929292931 |
| correct output |
|---|
| 129292929292929292929292929293... |
| user output |
|---|
| (empty) |
Test 3
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 292929292929292929292929292979 |
| correct output |
|---|
| 129292929292929292929292929297... |
| user output |
|---|
| (empty) |
