QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#242000#6395. Equation Discoveringucup-team902TL 0ms0kbC++145.4kb2023-11-06 21:04:482023-11-06 21:04:48

Judging History

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

  • [2023-11-06 21:04:48]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-11-06 21:04:48]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ull unsigned long long
#define db long 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] < 4){
            auto a = dfs(G[x][0]);
            if(a.size() != x_arr.size()){
                return a;
            }
            auto b = dfs(G[x][1]);
            if(b.size() != x_arr.size()){
                return b;
            }
            if(ops[x] == 0){
                return a + b;
            }
            if(ops[x] == 1){
                return a - b;
            }
            if(ops[x] == 2){
                return a * b;
            }
            if(ops[x] == 3){
                if(ops[G[x][1]] == -1){
                    return valarray<db>();
                }
                for(auto &v: b){
                    if(abs(v) < 1e-7){
                        return valarray<db>();
                    }
                }
                return a / b;
            }
        }
        else{
            auto a = dfs(G[x][0]);
            if(a.size() != x_arr.size()){
                return a;
            }
            if(ops[x] == 4){
                return sin(a);
            }
            if(ops[x] == 5){
                return cos(a);
            }
        }
        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);
        if(tmp.size() != x_arr.size()) return ;
        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;
}

詳細信息

Test #1:

score: 0
Time Limit Exceeded

input:

3
1.000000 1.000000
2.000000 4.000000
3.000000 9.000000

output:


result: