QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#104035#6395. Equation DiscoveringHe_Ren#WA 245ms91516kbC++142.4kb2023-05-08 12:14:092023-05-08 12:14:11

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-08 12:14:11]
  • 评测
  • 测评结果:WA
  • 用时:245ms
  • 内存:91516kb
  • [2023-05-08 12:14:09]
  • 提交

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;
const ldb ldbinf = 1e100;

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 y >= ldbinf / 2? ldbinf: sin(y);
	}
	
	if(type[u] == 'c')
	{
		auto y = calc(g[u][0], x);
		return y >= ldbinf / 2? ldbinf: cos(y);
	}
	
	auto l = calc(g[u][0], x);
	auto r = calc(g[u][1], x);
	
	if(l >= ldbinf / 2 || r >= ldbinf / 2)
		return NAN;
	
	if(type[u] == '+') return l + r;
	if(type[u] == '-') return l - r;
	if(type[u] == '*') return l * r;
	if(type[u] == '/') return fabs(r) >= 0.01? l / r: ldbinf;
	
	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(cur >= ldbinf / 2)
			{
				flag = 0;
				break;
			}
			if(fabs(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: 91428kb

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: 235ms
memory: 91416kb

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: 230ms
memory: 91336kb

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: 223ms
memory: 91408kb

input:

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

output:

(sin(x)/cos(x))

result:

ok great!!

Test #5:

score: 0
Accepted
time: 229ms
memory: 91516kb

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: -100
Wrong Answer
time: 230ms
memory: 91412kb

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-x))+x)

result:

wrong answer div a small number