QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#518213#7517. Flying Ship StoryKLPP#ML 0ms0kbC++171.5kb2024-08-13 18:17:422024-08-13 18:17:43

Judging History

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

  • [2024-08-13 18:17:43]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2024-08-13 18:17:42]
  • 提交

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

result: