QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#104030 | #6395. Equation Discovering | He_Ren# | WA | 249ms | 91520kb | C++14 | 2.3kb | 2023-05-08 11:59:40 | 2023-05-08 11:59:44 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ldb;
typedef pair<int,int> pii;
const int MAXP = 5e5 + 5;
int pcnt = 0;
int val[MAXP];
string s[MAXP];
char type[MAXP];
vector<int> g[MAXP];
ldb calc(int u,ldb x)
{
if(type[u] == 'x')
return x;
if(type[u] == 's')
{
auto y = calc(g[u][0], x);
return isnan(y)? NAN: sin(y);
}
if(type[u] == 'c')
{
auto y = calc(g[u][0], x);
return isnan(y)? NAN: cos(y);
}
auto l = calc(g[u][0], x);
auto r = calc(g[u][1], x);
if(isnan(l) || isnan(r))
return NAN;
if(type[u] == '+') return l + r;
if(type[u] == '-') return l - r;
if(type[u] == '*') return l * r;
if(type[u] == '/') return fabsl(r) >= 0.01? l / r: NAN;
return NAN;
}
int main(void)
{
set<string> bak;
auto push = [&] (int fir,string sec) -> int
{
if(bak.emplace(sec).second)
{
int u = ++pcnt;
val[u] = fir;
s[u] = sec;
return u;
}
return 0;
};
auto chk1 = [&] (int u)
{
if(val[u] + 1 > 9) return;
int v;
v = push(val[u] + 1, "sin(" + s[u] + ")");
if(v)
{
type[v] = 's';
g[v] = {u};
}
v = push(val[u] + 1, "cos(" + s[u] + ")");
if(v)
{
type[v] = 'c';
g[v] = {u};
}
};
auto chk2 = [&] (int l,int r)
{
if(val[l] + val[r] + 2 > 9) return;
const string oper = "+-*/";
for(auto t: oper)
{
if((t == '+' || t == '*') && s[l] > s[r]) continue;
int v = push(val[l] + val[r] + 2, "(" + s[l] + t + s[r] + ")");
if(v)
{
type[v] = t;
g[v] = {l,r};
}
}
};
push(0, "x");
type[1] = 'x';
vector< vector<int> > vec(10);
for(int u=1; u<=pcnt; ++u)
{
chk1(u);
vec[val[u]].emplace_back(u);
for(int i=0; i<=9 && val[u] + i + 2 <= 9; ++i)
for(auto oth: vec[i])
{
chk2(u, oth);
chk2(oth, u);
}
}
int n;
cin >> n;
vector< array<ldb,2> > p(n);
for(auto &t: p)
cin >> t[0] >> t[1];
for(int i=1; i<=pcnt; ++i)
{
bool flag = 1;
for(int j=0; j<n; ++j)
{
ldb x = p[j][0], y = p[j][1];
auto cur = calc(i, x);
if(isnan(cur))
{
flag = 0;
break;
}
if(fabsl(cur - y) / max((ldb)1, y) > 1e-3)
{
flag = 0;
break;
}
}
if(flag)
{
cout << s[i] << endl;
return 0;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 245ms
memory: 91520kb
input:
3 1.000000 1.000000 2.000000 4.000000 3.000000 9.000000
output:
(x*x)
result:
ok great!!
Test #2:
score: -100
Wrong Answer
time: 249ms
memory: 91420kb
input:
3 0.618000 1.517072 0.314000 3.132637 1.414000 0.494016
output:
(x/(x-x))
result:
wrong answer div a small number