QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#242002#6395. Equation Discoveringucup-team902WA 1884ms14932kbC++175.4kb2023-11-06 21:06:572023-11-06 21:06:58

Judging History

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

  • [2023-11-06 21:06:58]
  • 评测
  • 测评结果:WA
  • 用时:1884ms
  • 内存:14932kb
  • [2023-11-06 21:06:57]
  • 提交

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: 100
Accepted
time: 13ms
memory: 3852kb

input:

3
1.000000 1.000000
2.000000 4.000000
3.000000 9.000000

output:

((x-x)+(x*x))

result:

ok great!!

Test #2:

score: 0
Accepted
time: 21ms
memory: 3968kb

input:

3
0.618000 1.517072
0.314000 3.132637
1.414000 0.494016

output:

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

result:

ok great!!

Test #3:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

5
77.685777 233.057331
-66.445083 -199.335249
79.966717 239.900151
84.982130 254.946390
-31.528900 -94.586700

output:

((x+x)+x)

result:

ok great!!

Test #4:

score: 0
Accepted
time: 21ms
memory: 3964kb

input:

5
25.032427 -0.100652
38.727324 1.658518
27.684334 -0.669555
64.282391 8.275303
52.640700 -0.962660

output:

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

result:

ok great!!

Test #5:

score: 0
Accepted
time: 50ms
memory: 4300kb

input:

5
78.611917 -0.992212
-29.857271 1.011993
-75.513655 1.006611
68.512394 1.145128
7.961096 0.881661

output:

((sin(x)*sin(x))+cos(x))

result:

ok great!!

Test #6:

score: 0
Accepted
time: 23ms
memory: 4368kb

input:

5
-78.733375 0.503570
-20.187183 0.735779
-38.984992 0.730890
47.859232 0.622831
-19.657164 0.641512

output:

((x-x)+sin(sin(cos(cos(x)))))

result:

ok great!!

Test #7:

score: 0
Accepted
time: 19ms
memory: 3992kb

input:

5
3.241091 -32.628130
-83.514144 86.463432
33.586619 40.691607
41.123543 -147.352644
26.896326 27.404018

output:

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

result:

ok great!!

Test #8:

score: 0
Accepted
time: 1337ms
memory: 12708kb

input:

20
-4.908422 -0.693287
3.569189 0.328182
1.946572 -0.667466
6.515336 -0.829948
-1.394076 0.752980
6.722989 0.831881
1.241795 0.835231
-2.443177 -0.143098
-4.180762 -0.803482
1.511247 0.589509
0.627755 0.554244
-1.865604 -0.470029
-4.756347 -0.656984
1.850611 -0.426016
6.580133 -0.474416
6.861815 -0....

output:

sin(sin((x/sin((x/(x*x))))))

result:

ok great!!

Test #9:

score: 0
Accepted
time: 787ms
memory: 8608kb

input:

20
76.797930 0.000002
-76.263778 -0.000002
55.449039 0.000006
10.462093 0.000873
-78.051671 -0.000002
-52.781249 -0.000007
47.053973 0.000010
96.629212 0.000001
-40.697847 -0.000015
31.141805 0.000033
-87.087384 -0.000002
-54.709885 -0.000006
-65.741847 -0.000004
-87.430820 -0.000001
9.420126 0.0011...

output:

((x/(x*x))/(x*x))

result:

ok great!!

Test #10:

score: 0
Accepted
time: 1ms
memory: 4100kb

input:

20
24.490647 23.891773
17.327799 16.329001
21.204241 21.912414
83.489542 84.461510
-55.546573 -54.703972
-7.608368 -8.578356
-3.286697 -3.142101
-66.606831 -66.014954
-44.896454 -45.688502
97.541741 97.389961
-59.986043 -59.694554
57.723989 58.646803
-99.857351 -99.233536
29.134673 28.376609
-98.668...

output:

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

result:

ok great!!

Test #11:

score: 0
Accepted
time: 22ms
memory: 3948kb

input:

20
89.594917 88.596688
-45.187625 -44.253669
97.451471 97.513530
35.078537 35.576300
82.504351 81.771201
-49.755211 -50.243625
-23.019693 -23.876242
-45.247155 -44.293590
75.324114 75.398156
78.533049 78.526282
99.112156 100.100628
31.983437 31.445903
71.251578 70.407388
-44.178279 -43.983549
-25.28...

output:

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

result:

ok great!!

Test #12:

score: 0
Accepted
time: 585ms
memory: 8064kb

input:

20
16.664144 7.850741
44.708237 22.196248
-10.852343 1.533223
-42.713221 -12.119419
-27.815914 -11.038511
31.908696 13.299065
-82.394044 40.761558
-37.317157 -12.907073
-35.369997 17.659068
93.569121 -45.722539
-30.589159 -15.242258
16.180069 6.553209
56.572831 1.366451
99.591187 -47.440823
12.73229...

output:

((cos(x)*x)*sin(x))

result:

ok great!!

Test #13:

score: 0
Accepted
time: 21ms
memory: 3952kb

input:

20
-583.519562 0.000000
-169.653469 0.000000
372.798856 0.000000
180.084282 0.000000
139.388742 0.000000
-648.300263 0.000000
-859.523046 0.000000
-267.278551 0.000000
635.554372 0.000000
299.925737 0.000000
-628.299469 0.000000
169.393099 0.000000
556.144161 0.000000
-881.876627 0.000000
328.692044...

output:

((x-x)+(x-x))

result:

ok great!!

Test #14:

score: 0
Accepted
time: 0ms
memory: 3884kb

input:

20
746.491049 746.491049
414.031997 414.031997
-975.051138 -975.051138
45.313068 45.313068
-181.090458 -181.090458
119.607074 119.607074
245.794647 245.794647
-794.156219 -794.156219
461.647608 461.647608
-392.604379 -392.604379
384.522118 384.522118
-461.749513 -461.749513
766.462890 766.462890
244...

output:

x

result:

ok great!!

Test #15:

score: 0
Accepted
time: 1062ms
memory: 10016kb

input:

20
4.278335 0.092599
3.559350 0.559919
-2.517239 0.403581
-0.955317 0.182475
3.048015 0.888213
-0.638367 0.393205
-2.188885 0.183959
-0.367275 0.597938
1.106453 0.948186
0.339096 0.971773
-0.678258 0.364003
4.364111 0.060002
-0.671364 0.369012
-2.777257 0.600136
1.617698 0.909755
-3.400784 0.950952
...

output:

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

result:

ok great!!

Test #16:

score: -100
Wrong Answer
time: 1884ms
memory: 14932kb

input:

20
3.692126 -0.260752
0.663419 1.200876
1.167172 0.874743
4.852602 0.631308
3.373109 -0.334749
4.749943 0.529545
-2.549440 -0.245748
-1.158832 0.881804
4.115764 -0.040747
-3.401216 -0.330886
-4.320685 0.119451
-0.070540 1.332133
-4.666465 0.446117
-4.720184 0.499803
-1.731319 0.332854
4.232513 0.046...

output:


result:

wrong output format Unexpected end of file - token expected