QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#518213 | #7517. Flying Ship Story | KLPP# | ML | 0ms | 0kb | C++17 | 1.5kb | 2024-08-13 18:17:42 | 2024-08-13 18:17:43 |
answer
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long int lld;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
#define sz(a) (int)a.size()
typedef long double ld;
const long double PI = acos(-1.0L);
typedef complex<ld> cd;
vector<cd> fft(vector<cd> v){
int n=v.size();
vector<cd> ans(n);
rep(i,0,n){
rep(j,0,n){
cd w=(cd)polar(1.0L, (2*PI*i*j)/n);
ans[i]+=w*v[j];
}
}
return ans;
}
void solve(){
int n,k;
cin>>n>>k;
vector<lld> f(n);
rep(i,0,n){
cin>>f[i];
}
vector<cd> ft(n);
rep(i,0,n){
ft[i]=f[i];
}
vector<cd> cur=fft(ft);
vector<cd> pos(n);
pos[k]=1;
vector<cd> dif=fft(pos);
//trav(a,cur){
//cout<<fixed<<setprecision(10)<<abs(a)<<"\n";
//}
auto test=[&](lld x){
ld ans=0;
rep(i,0,n){
ans=max(ans,abs(dif[i]*((cd)x)+cur[i]));
}
return ans;
};
lld lo=-1e9;
lld hi=1e9;
while(hi-lo>10){
lld mid1=(hi+2*lo)/3;
lld mid2=(2*hi+lo)/3;
if(test(mid1)>test(mid2))lo=mid1;
else hi=mid2;
}
ld resp=test(lo);
for(lld i=lo+1;i<=hi;i++){
resp=min(resp,test(i));
}
cout<<fixed<<setprecision(10)<<resp<<"\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int tt=1;
//cin>>tt;
while(tt--){
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Memory Limit Exceeded
input:
5 1 2 3 1 1 4 5 2 2 2 2 2 3 7 2 3 4
output:
6.0000000000