QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#242002 | #6395. Equation Discovering | ucup-team902 | WA | 1884ms | 14932kb | C++17 | 5.4kb | 2023-11-06 21:06:57 | 2023-11-06 21:06:58 |
Judging History
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