QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#378541 | #6401. Classic: N Real DNA Pots | RainbowX# | WA | 1ms | 5964kb | C++20 | 2.5kb | 2024-04-06 13:30:18 | 2024-04-06 13:30:18 |
Judging History
answer
//#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define f(i, n, m) for (long long i = n; i <= m; ++i)
#define unf(i, n, m) for (long long i = n; i >= m; --i)
#define kong NULL
#define debug cout << "sss" << endl;
using ll = long long;
using ull = unsigned long long;
using point_t = double; // 计算几何的默认类型
const double e = exp(1.0);
const double pi = acos(-1.0);
constexpr ll inf = 0x3f3f3f3f3f3f3f3f;
constexpr ll maxx = 0x3f3f3f3f3f3f3f3f;
constexpr ll minn = 0xc0c0c0c0c0c0c0c0;
// #define endl '\n'
constexpr char blank = ' ';
constexpr ll mod = (ll)998244353;
constexpr size_t N = (size_t)1e6 + 6;
#ifdef _DEBUG
#define Crash(...) (__debugbreak(), 0)
#define Debug(...) (__debugbreak(), 0)
#else
#define Crash(...) (exit(-1), 0)
#define Debug(...) ((void)0)
#endif // _DEBUG
#define ensure(expression) (void)(!!(expression) || Crash())
inline void setaccuracy(const std::streamsize &accuracy)
{
std::cout << std::fixed << std::setprecision(accuracy);
}
#define int long long
using namespace std;
int n,k;
pair<int,int>que[100010];
priority_queue<pair<double,pair<int,int>>,vector<pair<double,pair<int,int>>>,greater<pair<double,pair<int,int>>>>quee;
int lianl[100010],lianr[100010];
double suan(int x,int y){
return (que[y].second-que[x].second)*1.0/(que[y].first-que[x].first);
}
void solve()
{
cin>>n>>k;
f(i,1,n)cin>>que[i].first>>que[i].second,lianl[i]=i-1,lianr[i]=i+1;
f(i,2,n){
quee.push({suan(i-1,i),{i-1,i}});
}
k=n-k;
while(k--){
auto op=quee.top();
quee.pop();
int L=lianl[op.second.first];
int R=lianr[op.second.second];
double a1=suan(L,op.second.second);
double a2=suan(L,op.second.second);
if(a1>a2){
lianr[L]=lianr[op.second.first];
lianl[op.second.second]=lianl[op.second.first];
if(L==0)continue;
quee.push({suan(L,op.second.second),{L,op.second.second}});
}
else {
lianr[op.second.first]=lianr[op.second.second];
lianl[R]=lianl[op.second.second];
if(R==n)continue;
quee.push({suan(op.second.first,R),{op.second.first,R}});
}
}
cout<<fixed<<setprecision(7)<<quee.top().first<<endl;
}
signed main()
{
// ios::sync_with_stdio(false);
// std::cin.tie(nullptr);
// std::cout.tie(nullptr);
int T = 1;
// cin >> T;
// scanf(" %d", &T);
// std::cin >> T;
// for (int q = 1; q <= T; q++) {
// while (T--) {
solve();
// }
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3820kb
input:
4 3 1 2 2 4 3 3 4 1
output:
-1.0000000
result:
ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 5840kb
input:
2 2 1 1 5 3
output:
0.5000000
result:
ok found '0.5000000', expected '0.5000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 5920kb
input:
2 2 222640995 547139825 489207317 725361095
output:
0.6685813
result:
ok found '0.6685813', expected '0.6685813', error '0.0000000'
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 5964kb
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:
-25.7815916
result:
wrong answer 1st numbers differ - expected: '3.7932105', found: '-25.7815916', error = '7.7967733'