CF2147I2

有简单的爆标做法，轻松构造出

n=1.2\times10^6

。

核心思路是有两个块

[l_1,r_1],[l_2,r_2]

，每块中的点距离为

1

，我们可以

l_2\to r_1\to l_2+1\to r_1-1\cdots

这样跳。

现在我们需要构造块间的转移。考虑倍增两个块的距离，比如设第

i

块的左端点为

2^{i+12}

（

+12

是为了给块长留空间）。这保证了对于一个两个点分别在块

a,b(a<b)

的点对，和一个在块

c,d(c<d)

的点对，按

b/d

为第一关键字，

a/c

为第二关键字就能比出来距离。因此我们直接枚举

i

从小到大，

j

从

i-1

到

0

，对块

(i,j)

往返跳即可。切换

i

或

j

时需要特殊处理一下，可以用一个距离比上一步大

1

的点中转。

现在已经可以构造出

n=6\times10^5

了。往返跳的过程还可以优化，将块内点的距离改为

k\geq4

，设

mid=\frac{(l_1+r_1)}2

，放两个中转点

mid+1,mid+2

，就可以

l_2\to mid+1\to r_1\to mid+2\to l_2+k\cdots

这样跳。这样可以让步数多一倍。下面是不精细的实现。

CPP

#include<bits/stdc++.h>
using namespace std;
const int d=12,bn=48,blen=290;
const long long inf=1e18;
int n,m,cnt;
long long p[bn+5][blen+5];
void out(long long x){
  cout<<x<<' ';
  if(!--n)exit(0);
}
int main(){
  cin>>n>>m;
  if(n==8&&m==6)return puts("1 1 3 6 10 3 11 1"),0;
  for(int i=1;i<=bn;i++)for(int j=0;j<=blen;j++)p[i][j]=(1ll<<(i+d))+j*5-inf;
  for(int i=3;i<=bn;i++){
    for(int j=i-2;j>=1;j--){
      long long mid=(p[j][blen]+p[i][0])/2;
      out(p[i][0]);
      for(int k=1;k<=blen;k++)out(mid+1),out(p[j][blen-k+1]),out(mid+2),out(p[i][k]);
      out(2*p[i][blen]-mid-1);
    }
  }
  return 0;
}

文章操作

相关推荐

评论

CF2147I2