QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#378541#6401. Classic: N Real DNA PotsRainbowX#WA 1ms5964kbC++202.5kb2024-04-06 13:30:182024-04-06 13:30:18

Judging History

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

  • [2024-04-06 13:30:18]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5964kb
  • [2024-04-06 13:30:18]
  • 提交

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'