QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#378789#6401. Classic: N Real DNA PotsDestiny#WA 3ms4068kbC++172.0kb2024-04-06 14:40:022024-04-06 14:40:03

Judging History

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

  • [2024-04-06 14:40:03]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:4068kb
  • [2024-04-06 14:40:02]
  • 提交

answer

#include<bits/stdc++.h>
#ifndef xxx
#define dbg(...) ;
#endif
using namespace std;
template<class T> ostream &operator<<(ostream &o, const vector <T> &v) { bool f=false; for(T i:v) { f?o<<' ':o; o<<(i); f=true; } return o; }
template<class T> void sort(T &v) { std::sort(v.begin(), v.end()); }
template<class T, class C> void sort(T &v, C c) { std::sort(v.begin(), v.end(), c); }
template<class T> void reverse(T &v) { std::reverse(v.begin(), v.end()); }
template<class T> bool is_sorted(T &v) { return std::is_sorted(v.begin(), v.end()); }
template<class T> inline void _min(T &x, const T &y) { x>y?x=y:x; }
template<class T> inline void _max(T &x, const T &y) { x<y?x=y:x; }
istream &operator>>(istream &i, __int128_t &x) { x=0; short f=1; char c=0; while(!isdigit(c)) { if(c=='-')f=-1; c=i.get(); } while(isdigit(c))x=x*10+c-'0', c=i.get(); x*=f; return i; }
ostream &operator<<(ostream &o, __int128_t x) { if(x==0) { o<<0; return o; } bool f=false; string s; if(x<0)f=true, x=-x; while(x)s+=x%10+'0', x/=10; reverse(s); if(f)o<<'-'; o<<s; return o; }
mt19937 mt(time(0));
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
constexpr int maxn=2e5+5;
constexpr int mod=1e9+7;
constexpr int inf=0x3f3f3f3f;
constexpr ll INF=0x3f3f3f3f3f3f3f3fll;
constexpr double pi=acos(-1.0);
constexpr double eps=1e-9;
pii p[maxn];
int main()//MARK: main
{
#ifndef xxx
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#endif
	cout<<fixed<<setprecision(10);
	int n, k;
	cin>>n>>k;
	for(int i=1; i<=n; i++)
		cin>>p[i].first>>p[i].second;
	auto check=[&](db m)->bool
	{
		set<db>se;
		for(int i=n; i>=k-1; i--)
		{
			auto [x, y]=p[i];
			db v=y-m*x;
			if(i<=n-1&&se.lower_bound(v)!=se.end())
			{
				return true;
			}
			se.insert(v);
		}
		return false;
	};
	db l=-inf, r=inf;
	for(int i=1; i<=60; i++)
	{
		db mid=(l+r)/2;
		if(check(mid))
		{
			l=mid;
		}
		else
		{
			r=mid;
		}
		if(l>r)break;
	}
	cout<<l<<'\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3852kb

input:

4 3
1 2
2 4
3 3
4 1

output:

-1.0000000009

result:

ok found '-1.0000000', expected '-1.0000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

2 2
1 1
5 3

output:

0.4999999995

result:

ok found '0.5000000', expected '0.5000000', error '0.0000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 4016kb

input:

2 2
222640995 547139825
489207317 725361095

output:

0.6685813430

result:

ok found '0.6685813', expected '0.6685813', error '0.0000000'

Test #4:

score: -100
Wrong Answer
time: 3ms
memory: 4068kb

input:

1000 20
545612 774435015
828317 212155588
5294705 85926095
5648835 764528941
6159263 570820268
7177330 744079287
8446124 162286636
8735551 586528841
9263030 524140841
9505706 636254627
12111352 182639083
12750780 238494418
13149143 913232250
13382784 11485121
13699797 414697815
14263990 423817548
15...

output:

74100.9373909232

result:

wrong answer 1st numbers differ - expected: '3.7932105', found: '74100.9373909', error = '19534.1505348'