QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#241957#6395. Equation Discoveringucup-team902WA 7ms4132kbC++144.7kb2023-11-06 20:19:122023-11-06 20:19:14

Judging History

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

  • [2023-11-06 20:19:14]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:4132kb
  • [2023-11-06 20:19:12]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ull unsigned long long
#define db double

valarray<db> x_arr;
valarray<db> y_arr;

map<int, ull> val;

struct tree{
    vector<vector<int>> G;
    vector<int>ops;
    vector<int>leaf;
    int comp;
    tree(){
        G.resize(1);
        ops.push_back(-1);
        leaf.push_back(0);
        comp = 0;
    }
    tree(const tree &T, int x, int op){
        G = T.G;
        ops = T.ops;
        for(auto &v: T.leaf){
            if(v != x){
                leaf.push_back(v);
            }
        }
        comp = T.comp;
        assert(ops[x] == -1);
        assert(G[x].empty());
        ops[x] = op;
        if(op < 4){
            int u = G.size();
            int v = G.size() + 1;
            G.resize(G.size() + 2);
            G[x].push_back(u);
            G[x].push_back(v);
            ops.push_back(-1);
            ops.push_back(-1);
            leaf.push_back(u);
            leaf.push_back(v);
            comp += 2;
        }
        else{
            int u = G.size();
            G[x].push_back(u);
            G.resize(G.size() + 1);
            ops.push_back(-1);
            leaf.push_back(u);
            comp += 1;
        }
    }

    valarray<db> dfs(int x) const{
        if(ops[x] == -1){
            return x_arr;
        }
        if(ops[x] == 0){
            return dfs(G[x][0]) + dfs(G[x][1]);
        }
        if(ops[x] == 1){
            return dfs(G[x][0]) - dfs(G[x][1]);
        }
        if(ops[x] == 2){
            return dfs(G[x][0]) * dfs(G[x][1]);
        }
        if(ops[x] == 3){
            return dfs(G[x][0]) / dfs(G[x][1]);
        }
        if(ops[x] == 4){
            return sin(dfs(G[x][0]));
        }
        if(ops[x] == 5){
            return cos(dfs(G[x][0]));
        }
        assert(0);
    }

    void out(int x) const{
        if(ops[x] == -1){
            putchar('x');
            return ;
        }
        if(ops[x] == 0){
            putchar('(');
            out(G[x][0]);
            putchar('+');
            out(G[x][1]);
            putchar(')');
            return ;
        }
        if(ops[x] == 1){
            putchar('(');
            out(G[x][0]);
            putchar('-');
            out(G[x][1]);
            putchar(')');
            return ;
        }
        if(ops[x] == 2){
            putchar('(');
            out(G[x][0]);
            putchar('*');
            out(G[x][1]);
            putchar(')');
            return ;
        }
        if(ops[x] == 3){
            putchar('(');
            out(G[x][0]);
            putchar('/');
            out(G[x][1]);
            putchar(')');
            return ;
        }
        if(ops[x] == 4){
            printf("sin(");
            out(G[x][0]);
            printf(")");
            return ;
        }
        if(ops[x] == 5){
            printf("cos(");
            out(G[x][0]);
            printf(")");
            return ;
        }
        assert(0);
    }

    void check() const{
        auto tmp = dfs(0);
        for(int i = 0; i < x_arr.size(); ++i){
            if(tmp[i] != tmp[i]) return ;
            // if(abs(tmp[i] - y_arr[i]) > 1e-7) return ;
            if(round(tmp[i] * 1e6) != round(y_arr[i] * 1e6)){
                return ;
            }
        }
        out(0);
        puts("");
        exit(0);
    }

    ull Hash(int x = 0) const{
        ull ret = val[ops[x]];
        if(ops[x] == 1 || ops[x] == 3){
            for(auto &v: G[x]){
                ull t = Hash(v);
                ret = ret * 137 + t * t * t;
            }
        }
        else{
            for(auto &v: G[x]){
                ull t = Hash(v);
                ret = ret + t * t * t;
            }
        }
        return ret;
    }
};

unordered_set<ull> vis;

void dfs(tree T0, int lst){
    if(T0.comp > 9){
        return ;
    }
    ull state = T0.Hash();
    if(vis.find(state) != vis.end()) return ;
    T0.check();
    vis.insert(state);
    for(auto &x: T0.leaf){
        if(x <= lst) continue;
        for(int i = 0; i < 4; ++i){
            dfs(tree(T0, x, i), x);
        }
        for(int i = 4; i < 6; ++i){
            dfs(tree(T0, x, i), x);
        }
    }
}

int main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    for(int i = -1; i < 6; ++i){
        val[i] = ((ull)rand() << 32) | (ull)rand();
    }
    int n; scanf("%d", &n);
    x_arr.resize(n);
    y_arr.resize(n);
    for(int i = 0; i < n; ++i){
        db x, y; scanf("%lf%lf", &x_arr[i], &y_arr[i]);
    }
    dfs(tree(), -1);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 7ms
memory: 4132kb

input:

3
1.000000 1.000000
2.000000 4.000000
3.000000 9.000000

output:

((x+x)+sin((x/(x-x))))

result:

wrong answer div a small number