QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#254104 | #1294. Equality Control | Fyind | WA | 96ms | 132936kb | C++20 | 4.1kb | 2023-11-18 00:44:22 | 2023-11-18 00:44:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
typedef long long ll;
typedef long double ld;
#define sz(x) ((int)x.size())
typedef pair<int,int> pii;
#define _ << " " <<
struct Node {
vector<int> c;
vector<pii> sh;
};
int tot;
Node t[maxn];
struct SN {
string op="";
deque<int> v;
int siz=0;
};
SN zero;
SN parse(string &x) {
list<SN> st;
auto parseList = [&]() {
stringstream ss(st.back().op);
char c; int x; ss >> c;
st.back().v.push_back(0);
while (!ss.eof()) {
ss >> x;
st.back().v.push_back(x);
st.back().siz++;
ss >> c;
}
};
auto parseOp = [&]() {
string name;
auto it = --st.end();
auto it2 = it; --it2;
auto it3 = it2;
if (it2->op[0] == '[') {
--it3;
name = it3->op;
} else name = it2->op;
if (name == "concat") {
// it2, it1
if (it2->v.size() < it->v.size()) {
while (!it2->v.empty()) {
it->v.push_front(it2->v.back());
it2->v.pop_back();
}
it->siz += it2->siz;
st.erase(it2);
} else {
while (!it->v.empty()) {
it2->v.push_back(it->v.front());
it->v.pop_front();
}
it2->siz += it->siz;
st.erase(it);
}
st.erase(--(--st.end()));
} else if (name == "shuffle") {
st.erase(it2);
st.back().v.front() = -st.back().siz;
} else if (name == "sorted") {
st.erase(it2);
st.back().v.front() = INT_MAX - st.back().siz;
}
};
st.push_back(zero);
int open = 0;
for (int i = 0;i < sz(x); ++i) {
if (x[i] == ']') {
parseList();
open = 0;
} else if (x[i] == ')') {
parseOp();
} else if (x[i] == '('){
st.push_back(zero);
} else if (x[i] == '['){
st.back().op.push_back(x[i]);
open = 1;
} else if (x[i] == ',' && !open) {
st.push_back(zero);
} else {
st.back().op += x[i];
}
}
// for (auto x : st.back().v) cout << x << endl;
return st.back();
}
bool cmp(SN a, SN b) {
int id = 0;
auto gen = [&](SN &a,vector<pii> &sha, vector<int> &ans) {
int i = 0;
for (;i < sz(a.v); ++i) {
int x = a.v[i];
if (x < 0) {
int siz = -x;
int pre = -1; int ok = 1;
for (int j = 0;j < siz; ++i) {
if (a.v[i] > 0 && a.v[i] <= 1e9) {
ans.push_back(a.v[i]);
j++;
if (pre == -1) pre = a.v[i];
else if (pre != a.v[i]) ok = 0;
}
}
if (!ok) sha.push_back({sz(ans)-siz, ans.size()});
} else if (x > 1e9) {
int siz = INT_MAX - x;
for (int j = 0;j < siz; ++i) {
if (a.v[i] > 0 && a.v[i] <= 1e9) {
ans.push_back(a.v[i]);
j++;
}
}
sort(ans.end()-siz, ans.end());
} else if (x > 0){
ans.push_back(x);
}
}
};
vector<pii> sa, sb;
vector<int> ansa, ansb;
gen(a,sa, ansa);
gen(b,sb, ansb);
sort(sa.begin(), sa.end());
sort(sb.begin(),sb.end());
return sa == sb && ansa == ansb;
}
int main() {
#ifdef LLOCAL
freopen("a.in", "r", stdin);
#endif
ios_base::sync_with_stdio(0); cin.tie(0);
string a, b; cin >> a >> b;
auto ta = parse(a);
auto tb = parse(b);
if (cmp(ta,tb)) {
cout <<"equal" << '\n';
} else {
cout << "not equal" << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 8316kb
input:
sorted([100,99]) [100,99]
output:
not equal
result:
ok single line: 'not equal'
Test #2:
score: 0
Accepted
time: 9ms
memory: 8768kb
input:
concat(concat(concat(concat(concat(shuffle([8254,5182]),concat(concat([3315],shuffle([6482,2407])),concat([3784],[7750]))),[5375,131,3163,3723,8518]),concat(concat(concat(shuffle([8959,3233,9777,1232]),concat(concat([3838],[5920]),concat([1184],shuffle([2034,6261,7379,2266,9127,6950,5741])))),[3050]...
output:
not equal
result:
ok single line: 'not equal'
Test #3:
score: 0
Accepted
time: 1ms
memory: 8232kb
input:
concat([908343,225257],concat([655775,182386,87829,448344],[947476,877175,818928,621687])) concat([908343,225257,655775,182385],concat([87829,448345],[947476,877175,818928,621687]))
output:
not equal
result:
ok single line: 'not equal'
Test #4:
score: 0
Accepted
time: 0ms
memory: 8472kb
input:
concat(concat([94912,69780],[424582,392292,486324]),concat(concat(concat(concat([247951,75666,677977],[215906,167644,135405]),concat([814116,550601],concat([901479,985210],[28105,270616,255829]))),concat(concat([569437,649640],concat([281626,939656],[987060,269413,155848])),concat(concat([249742,626...
output:
not equal
result:
ok single line: 'not equal'
Test #5:
score: 0
Accepted
time: 0ms
memory: 8264kb
input:
concat(concat(concat([922379,476070],concat(concat([315410,476729,540590],[556639,73661,652252]),concat([338704,919470,740250],[172699,257489,893514]))),concat([413930,107863],concat([978894,47571],concat([497594,370537,499878],concat(concat([146624,748528,622848],[1575,29409,291670]),concat(concat(...
output:
equal
result:
ok single line: 'equal'
Test #6:
score: 0
Accepted
time: 2ms
memory: 8336kb
input:
concat(concat(concat(concat(concat([179688,283590],concat([908649,8053],concat([526442,518453],[543916,359201,273765]))),concat(concat([187273,252097,862202,619925],concat([885812,19337,102809],[479628,328955,174259])),concat(concat([310303,702921,137859],[909923,229256,29748]),concat([276494,186268...
output:
not equal
result:
ok single line: 'not equal'
Test #7:
score: 0
Accepted
time: 0ms
memory: 8276kb
input:
concat(concat(concat(concat([263362,562526,889508,55758],[124266,356296,662685,484630]),concat(concat(concat(concat([462468,172858,106505],[388420,325703,703986]),concat([751266,230723],[112856,683192,589997,589179])),concat(concat([619823,88799],concat([895544,357238,501106],concat([923477,278671],...
output:
equal
result:
ok single line: 'equal'
Test #8:
score: 0
Accepted
time: 0ms
memory: 8524kb
input:
shuffle([1,1,1,1]) sorted([1,1,1,1])
output:
equal
result:
ok single line: 'equal'
Test #9:
score: 0
Accepted
time: 2ms
memory: 8332kb
input:
shuffle([1,1,1,1,1,1,1,1,1,1,1]) [1,1,1,1,1,1,1,1,1,1,1]
output:
equal
result:
ok single line: 'equal'
Test #10:
score: 0
Accepted
time: 15ms
memory: 16528kb
input:
sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted...
output:
not equal
result:
ok single line: 'not equal'
Test #11:
score: 0
Accepted
time: 47ms
memory: 69948kb
input:
sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted(sorted...
output:
equal
result:
ok single line: 'equal'
Test #12:
score: 0
Accepted
time: 2ms
memory: 8312kb
input:
concat(shuffle([1,2,3]),concat(shuffle([3]),shuffle([1,2]))) concat(shuffle([2,3]),concat(shuffle([1]),shuffle([1,2,3])))
output:
not equal
result:
ok single line: 'not equal'
Test #13:
score: 0
Accepted
time: 2ms
memory: 8312kb
input:
concat(shuffle([1,2,3]),concat(shuffle([1]),shuffle([2,3]))) concat(shuffle([1,2]),concat(shuffle([3]),shuffle([1,2,3])))
output:
not equal
result:
ok single line: 'not equal'
Test #14:
score: 0
Accepted
time: 0ms
memory: 8316kb
input:
concat([1,1],[1]) concat([1],[1,1])
output:
equal
result:
ok single line: 'equal'
Test #15:
score: 0
Accepted
time: 81ms
memory: 102308kb
input:
concat(concat([2],concat(concat([8],concat(concat([1],concat(concat([8],concat(concat([6],concat(concat([8],concat(concat([2],concat(concat([4],concat(concat([7],concat(concat([2],concat(concat([6],concat(concat([5],concat(concat([6],concat(concat([8],concat(concat([6],concat(concat([5],concat(conca...
output:
equal
result:
ok single line: 'equal'
Test #16:
score: 0
Accepted
time: 0ms
memory: 8316kb
input:
concat(shuffle([1,2]),shuffle([3,4])) shuffle([1,2,3,4])
output:
not equal
result:
ok single line: 'not equal'
Test #17:
score: 0
Accepted
time: 2ms
memory: 8260kb
input:
concat(shuffle([3,4]),shuffle([1,2])) shuffle([1,2,3,4])
output:
not equal
result:
ok single line: 'not equal'
Test #18:
score: 0
Accepted
time: 1ms
memory: 8460kb
input:
sorted(concat(shuffle([1,2]),[1])) [1,1,2]
output:
equal
result:
ok single line: 'equal'
Test #19:
score: 0
Accepted
time: 63ms
memory: 71812kb
input:
concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat...
output:
not equal
result:
ok single line: 'not equal'
Test #20:
score: 0
Accepted
time: 93ms
memory: 132936kb
input:
concat([2],concat([1],concat([9],concat([1],concat([7],concat([4],concat([5],concat([5],concat([7],concat([9],concat([7],concat([2],concat([2],concat([6],concat([3],concat([2],concat([8],concat([1],concat([5],concat([7],concat([9],concat([6],concat([7],concat([3],concat([4],concat([4],concat([2],con...
output:
not equal
result:
ok single line: 'not equal'
Test #21:
score: 0
Accepted
time: 45ms
memory: 70224kb
input:
concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat...
output:
equal
result:
ok single line: 'equal'
Test #22:
score: 0
Accepted
time: 78ms
memory: 71600kb
input:
sorted(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat(concat...
output:
not equal
result:
ok single line: 'not equal'
Test #23:
score: 0
Accepted
time: 96ms
memory: 132932kb
input:
sorted(concat([1],concat([9],concat([1],concat([7],concat([4],concat([5],concat([5],concat([7],concat([9],concat([7],concat([2],concat([2],concat([6],concat([3],concat([2],concat([8],concat([1],concat([5],concat([7],concat([9],concat([6],concat([7],concat([3],concat([4],concat([4],concat([2],concat(...
output:
not equal
result:
ok single line: 'not equal'
Test #24:
score: 0
Accepted
time: 2ms
memory: 8452kb
input:
[9] [9]
output:
equal
result:
ok single line: 'equal'
Test #25:
score: 0
Accepted
time: 2ms
memory: 8312kb
input:
[6] [7]
output:
not equal
result:
ok single line: 'not equal'
Test #26:
score: 0
Accepted
time: 1ms
memory: 8536kb
input:
shuffle([23,42]) [23,42]
output:
not equal
result:
ok single line: 'not equal'
Test #27:
score: 0
Accepted
time: 2ms
memory: 8524kb
input:
shuffle([23,42]) [42,23]
output:
not equal
result:
ok single line: 'not equal'
Test #28:
score: -100
Wrong Answer
time: 1ms
memory: 8324kb
input:
shuffle([1,1,1,1,1,1,1,1,1,2]) shuffle([2,1,1,1,1,1,1,1,1,1])
output:
not equal
result:
wrong answer 1st lines differ - expected: 'equal', found: 'not equal'