QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#104030#6395. Equation DiscoveringHe_Ren#WA 249ms91520kbC++142.3kb2023-05-08 11:59:402023-05-08 11:59:44

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 11:59:44]
  • 评测
  • 测评结果:WA
  • 用时:249ms
  • 内存:91520kb
  • [2023-05-08 11:59:40]
  • 提交

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