# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
124504 | andreiomd | Zamjena (COCI18_zamjena) | C++11 | 662 ms | 9044 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <cstring>
#include <map>
using namespace std;
const int NMAX = 5e4 + 5, MMAX = 15, LIM = 3e5;
int N, M, n;
char S[MMAX];
bool OK = true;
struct Element
{
int X;
char Y[MMAX];
};
Element A[NMAX], B[NMAX];
map < string, int > mp;
map < string, bool > Sel;
inline void Read ()
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cin >> N;
for(int i = 1; i <= N; ++i)
{
cin >> (S + 1);
M = strlen(S + 1);
bool Nr = true;
for(int j = 1; j <= M && Nr; ++j)
if(!isdigit(S[j]))
Nr = false;
if(Nr)
{
n = 0;
for(int j = 1; j <= M; ++j)
n = n * 10 + (S[j] - '0');
A[i].X = n;
}
else
for(int j = 1; j <= M; ++j)
A[i].Y[j] = S[j];
}
for(int i = 1; i <= N; ++i)
{
cin >> (S + 1);
M = strlen(S + 1);
bool Nr = true;
for(int j = 1; j <= M && Nr; ++j)
if(!isdigit(S[j]))
Nr = false;
if(Nr)
{
n = 0;
for(int j = 1; j <= M; ++j)
n = n * 10 + (S[j] - '0');
B[i].X = n;
}
else
for(int j = 1; j <= M; ++j)
B[i].Y[j] = S[j];
}
return;
}
inline void Solve ()
{
for(int i = 1; i <= N; ++i)
if(A[i].X && B[i].X)
if(A[i].X != B[i].X)
{
OK = false;
break;
}
if(!OK)
return;
bool done = true;
int op = 0;
while(done && op * N <= LIM)
{
++op;
done = false;
for(int i = 1; i <= N; ++i)
if(A[i].X && B[i].X)
continue;
else
{
if(A[i].X)
{
string V;
M = strlen(B[i].Y + 1);
for(int j = 1; j <= M; ++j)
V.push_back(B[i].Y[j]);
if(Sel[V])
{
if(mp[V] != A[i].X)
{
OK = false;
return;
}
else
continue;
}
else
{
Sel[V] = true;
mp[V] = A[i].X;
}
}
else
{
if(B[i].X)
{
string V;
M = strlen(A[i].Y + 1);
for(int j = 1; j <= M; ++j)
V.push_back(A[i].Y[j]);
if(Sel[V])
{
if(mp[V] != B[i].X)
{
OK = false;
return;
}
else
continue;
}
else
{
Sel[V] = true;
mp[V] = B[i].X;
}
}
else
{
if(strcmp(A[i].Y + 1, B[i].Y + 1) == 0)
continue;
string V1, V2;
int m1 = (int)strlen(A[i].Y + 1);
int m2 = (int)strlen(B[i].Y + 1);
for(int j = 1; j <= m1; ++j)
V1.push_back(A[i].Y[j]);
for(int j = 1; j <= m2; ++j)
V2.push_back(B[i].Y[j]);
if(Sel[V1] && Sel[V2])
{
if(mp[V1] != mp[V2])
{
OK = false;
return;
}
else
continue;
}
else
{
if(Sel[V1])
{
Sel[V2] = true;
mp[V2] = mp[V1];
}
else
{
if(Sel[V2])
{
Sel[V1] = true;
mp[V1] = mp[V2];
}
else
done = true;
}
}
}
}
}
}
return;
}
int main()
{
Read();
Solve();
if(OK)
cout << "DA";
else
cout << "NE";
cout << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |