QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#242000 | #6395. Equation Discovering | ucup-team902 | TL | 0ms | 0kb | C++14 | 5.4kb | 2023-11-06 21:04:48 | 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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
3 1.000000 1.000000 2.000000 4.000000 3.000000 9.000000