QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#225407#7512. Almost Prefix ConcatenationPetroTarnavskyi#WA 0ms3812kbC++172.2kb2023-10-24 17:01:422023-10-24 17:01:43

Judging History

你现在查看的是最新测评结果

  • [2023-10-24 17:01:43]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3812kb
  • [2023-10-24 17:01:42]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const db pi = acos(-1);
const db INF = 1e9;
const db EPS = -1e6;


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(15);
	
	int n, k;
	cin >> n >> k;
	VI f(n);
	FOR (i, 0, n)
		cin >> f[i];
	vector<vector<db>> coef(n, vector<db>(4, 0));
	FOR (i, 0, n)
	{
		FOR (j, 0, n)
		{
			db alpha = -2 * pi * i * j / n;
			db p = cos(alpha);
			db q = sin(alpha);
			if (j == k)
			{
				coef[i][0] += p;
				coef[i][2] += q;
			}
			else
			{
				coef[i][1] += f[j] * p;
				coef[i][3] += f[j] * q;
			}
		}
	}
	db L = 0, R = INF;
	FOR (iter, 0, 1)//74)
	{
		db m = (L + R) / 2;
		m = 2;
		db l = -INF, r = INF;
		bool ok = true;
		FOR (i, 0, n)
		{
			db a = coef[i][0] * coef[i][0] + coef[i][2] * coef[i][2];
			db b = 2 * coef[i][0] * coef[i][1] + 2 * coef[i][2] * coef[i][3];
			db c = coef[i][1] * coef[i][1] + coef[i][3] * coef[i][3] - m * m;
			
			db mn = -INF;
			if (abs(a) > EPS)
				mn = -b / (2 * a);
			if (a * mn * mn + b * mn + c > 0)
			{
				ok = false;
				break;
			}
			db ll = -INF;
			db cpmn = mn;
			FOR (j, 0, 74)
			{
				db mm = (ll + cpmn) / 2;
				if (a * mm * mm + b * mm + c < 0)
					cpmn = mm;
				else
					ll = mm;
			}
			db rr = INF;
			cpmn = mn;
			FOR (j, 0, 74)
			{
				db mm = (rr + cpmn) / 2;
				if (a * mm * mm + b * mm + c < 0)
					cpmn = mm;
				else
					rr = mm;
			}
			cout << a << " " << b << " " << c << endl;
			cout << a * ll * ll + b * ll + c  << endl;
			cout << a * rr * rr + b * rr + c  << endl;
			cout << i << " " << ll << " " << rr << endl;
			l = max(l, ll);
			r = min(r, rr);
		}
		cerr << ok << " " << l << " " << r << endl;
		//return 0;
		if (ok && l < r)
			R = m;
		else
			L = m;
	}
	cout << L << '\n';
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3812kb

input:

ababaab
aba

output:

0.000000000000000

result:

wrong output format Expected integer, but "0.000000000000000" found