[ABC344G] Points and Comparison 题解

FFTotoro · 2024-03-10 17:23:41 · 题解

其实这题暴力可以过的。参考 MMNMM 的解法。

发现数据范围很大，容易被卡时或者卡精度。于是考虑用浮点数处理，具体地，对于一个询问 (A,B)，令 B_1=\mathrm{lsh}(\mathrm{rsh}(B,31),31),B_2=B-\mathrm{lsh}(\mathrm{rsh}(B,31),31)，其中 \mathrm{lsh}(x,y) 表示 x 左移 y 位，\mathrm{rsh} 同理。结合 cmath 中的一个函数叫做 fma(x,y,z)（返回值是 xy+z，可以满足精度需求），则 f(A,B)=\sum\limits_{i=1}^N[Y_i-B_2\ge\mathrm{fma}(A,X_i,B_1)]。

但是上面的做法太慢了。于是我们考虑指令集优化；指令集中有个很开挂的东西叫做 avx512f。AVX-512 指令集相关内容可以参考这里。

再加上一些常规卡常技巧（例如使用 const），时间复杂度为 O(NQ) 的暴力可以直接通过。

放代码：

#pragma GCC optimize("Ofast,unroll-loop")
#pragma GCC target("avx512f")
#include<bits/stdc++.h>
using namespace std;
const long P=(1ll<<31)-1;
double x[5000],y[5000];
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n; cin>>n;
  for(int i=0;i<n;i++)cin>>x[i]>>y[i];
  int q; long g0,ra,rb,c=0; cin>>q>>g0>>ra>>rb;
  auto G=[&](){return (g0*=48271)%=P;};
  while(q--){
    const long g1=G(),g2=G(),g3=G(),b=-rb+(g2*P+g3)%(rb<<1|1);
    const double a=-ra+g1%(ra<<1|1),b1=(b>>31)<<31,b2=b-((b>>31)<<31);
    for(int i=0;i<n;i++)c+=y[i]-b2>=fma(a,x[i],b1);
  }
  cout<<c<<endl;
  return 0;
}