QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#104267#6395. Equation DiscoveringMelacau#RE 2ms3952kbC++172.8kb2023-05-09 21:19:192023-05-09 21:19:23

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-09 21:19:23]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:3952kb
  • [2023-05-09 21:19:19]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std; namespace {
    using T = long double;
    const char endl = '\n';
    const int maxN = 1e6 + 5;
    const string uops = "sc";
    const string bops = "+-*/";

    using Arr = array<T, 21>;

    int n;
    Arr x, y;
    struct S { char op; int ld, li, rd, ri; Arr x; };
    vector<S> f[10];

    Arr uop(char op, const Arr& a) { 
        Arr ret;
        if(op == 's') for(int i = 1; i <= n; i++) ret[i] = sin(a[i]);
        if(op == 'c') for(int i = 1; i <= n; i++) ret[i] = cos(a[i]);
        return ret;
    }
    pair<Arr, bool> bop(char op, const Arr& a, const Arr& b) {
        Arr ret;
        if(op == '+') for(int i = 1; i <= n; i++) ret[i] = a[i] + b[i];
        if(op == '-') for(int i = 1; i <= n; i++) ret[i] = a[i] - b[i];
        if(op == '*') for(int i = 1; i <= n; i++) ret[i] = a[i] * b[i];
        if(op == '/') {
            for(int i = 1; i <= n; i++) if(b[i] < 0.01) return { Arr{}, false };
            for(int i = 1; i <= n; i++) ret[i] = a[i] / b[i];
        }
        return { ret, true };
    }
    T diff(const Arr& a) {
        T ret = 0;
        for(int i = 1; i <= n; i++) 
            ret = max(ret, abs(a[i] - y[i]) / max<T>(1, abs(y[i])));
        return ret;
    }

    void print(const S& s, bool fst = true) {
        if(s.op == 'x') return cout << 'x', void();
        if(s.op == 's') return cout << "sin(", print(f[s.ld][s.li], false), cout << ')', void();
        if(s.op == 'c') return cout << "cos(", print(f[s.ld][s.li], false), cout << ')', void();
        if(!fst) cout << '(';
        print(f[s.ld][s.li], false);
        cout << s.op;
        print(f[s.rd][s.ri], false);
        if(!fst) cout << ')';
    }
   
    void solve() {  
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> x[i] >> y[i];
        f[0].push_back(S{ 'x', -1, -1, -1, -1, x });
        for(int d = 1; d <= 9; d++) {
            for(int i = 0; i < f[d - 1].size(); i++) 
                for(char op : uops) 
                    f[d].push_back(S{ op, d - 1, i, -1, -1, uop(op, f[d - 1][i].x) });
            for(int ld = 0, rd = d - 2; ld <= d - 2; rd = d - ++ld - 2) 
                for(int li = 0; li < f[ld].size(); li++)
                    for(int ri = 0; ri < f[rd].size(); ri++) 
                        for(char op : bops) {
                            auto [x, ok] = bop(op, f[ld][li].x, f[rd][ri].x);
                            if(!ok) continue;
                            f[d].push_back(S{ op, ld, li, rd, ri, x });
                        }
            for(auto& s : f[d]) if(diff(s.x) < 1e-3) {
                print(s);
                return;
            }
        }   
        cout << "??";
        abort();
    }   
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1; // cin >> t;
    for(int i = 1; i <= t; i++) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3548kb

input:

3
1.000000 1.000000
2.000000 4.000000
3.000000 9.000000

output:

x*x

result:

ok great!!

Test #2:

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

input:

3
0.618000 1.517072
0.314000 3.132637
1.414000 0.494016

output:

sin(x)/(x*x)

result:

ok great!!

Test #3:

score: 0
Accepted
time: 2ms
memory: 3596kb

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: -100
Dangerous Syscalls

input:

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

output:


result: