QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#254104#1294. Equality ControlFyindWA 96ms132936kbC++204.1kb2023-11-18 00:44:222023-11-18 00:44:23

Judging History

你现在查看的是最新测评结果

  • [2023-11-18 00:44:23]
  • 评测
  • 测评结果:WA
  • 用时:96ms
  • 内存:132936kb
  • [2023-11-18 00:44:22]
  • 提交

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'