QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#225407 | #7512. Almost Prefix Concatenation | PetroTarnavskyi# | WA | 0ms | 3812kb | C++17 | 2.2kb | 2023-10-24 17:01:42 | 2023-10-24 17:01:43 |
Judging History
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