数据生成器：

#include<iostream>
using namespace std;
const int N=987765;
int main(){
    freopen("array20.in","w",stdout);
    cout<<N<<"\n";
    return 0;
} 

checker

#include<cmath>
#include<cstdio>
#include"testlib_for_lemons.h"
#include<iostream>
#include<map>
#define ll long long
using namespace std;
const int N=1e6+5;
int a[N];
ll b[N];
map<int,int> f;
map<ll,int> g;
int main(int argc,char *argv[]) {
    registerLemonChecker(argc,argv);
    int n,m,p;
    n=inf.readInt();
    m=ouf.readInt();
    p=ans.readInt();
    int fullscore=perfectScore;
    for(int i=1;i<=n;i++){
        a[i]=ouf.readInt();
        if(a[i]<1||a[i]>300000){
            quitf(_wa,"Wrong Answer: Invalid a:a[%d] out of range\n",i);
            return 0;
        }
    }
    for(int i=1;i<n;i++) b[i]=1ll*a[i]*a[i+1];
    int rm=0,fl=0;
    int l=0,r=0;
    for(int i=1;i<=n;i++){
        f[a[i]]++;
        if(f[a[i]]==1) rm++;
        if(g[b[i]]>1){
            fl=1;
            l=g[b[i]];
            r=i;
        }
        if(i<n) g[b[i]]=i;
    }
    int x=atoi(argv[4]); 
    if(rm!=m){
        quitf(_wa,"Wrong Answer: Distinct elements of a differs from your m\n");
        return 0;
    }
    if(fl){
        if(m==p) quitp(0.2*fullscore,"Partial Result: Invalid a but optimal m\n");
        else quitf(_wa,"Wrong Answer: Invalid a\n");
        return 0;
    }
    if(m>2*p) quitp(0.2*fullscore,"Partial Result: 20%. Optimal m is %d,your m is %d\n",p,m);
    else if(m>p+1) quitp(0.4*fullscore,"Partial Result: 40%. Optimal m is %d,your m is %d\n",p,m);
    else if(m==p+1) quitp(0.6*fullscore,"Partial Result: 60%. Optimal m is %d,your m is %d\n",p,m);
    else if(m==p) quitf(_ok,"Perfect Result. You can get all points in this test case!");
    else quitf(_ok,"You reach lvl61 in Genshin Impact!"); 
    return 0;
}

CF1981D

考虑若 \(a_i\) 均为质数，则 \(a_ia_{i+1}=a_ja_{j+1}\) 等价于无序对 \((a_i,a_{i+1})=(a_j,a_{j+1})\) 。以下设 \(a_i=p_{x_i}\) ，其中 \(p_i\) 为第 \(i\) 个质数。

考虑 \(\forall i \neq j\) , \((i,j)\) 间有无向边的图 \(G\) ，则原题等价于选出一条 \(n\) 个点的路径，不重复经过一条边，最小化经过的节点数。

显然有单调性，考虑对一个给定的 \(u\) ，如何判断 \(u\) 个点的完全图中是否存在合法路径。

若 \(u\) 为奇数，则所有点的出度均为偶数，此时图中必定存在一条欧拉路径，这时 \(u\) 合法等价于 \(n\le \dfrac{u(u-1)}{2}\) 。

若 \(u\) 为偶数，则所有点的出度均为奇数，考察图中欧拉路径的最大长度，若删去 \((1,2),(3,4) \dots (n-3,n-2)\) 这些边，仅有 \(n-1,n\) 这两个点度数为奇数，存在欧拉路径。另一方面，原图中有 \(n\) 个奇点，删除一条边最多减少 \(2\) 个，因此至少删除 \(\dfrac{u}{2}-1\) 条边。因此，此时 \(u\) 合法等价于 \(n \le \dfrac{u(u-2)}{2}+1\) 。

找到最大的 \(u\) ，求出该图的欧拉路径即可。\(u\) 最大为 \(1415\) ，而第 \(1415\) 个质数远小于 \(3 \times 10^5\) ，因此构造合法。

std

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int t,n;
const int N=2e6+5;
int a[N],p[N],ip[N],c[N],tr[N],cnt;
int ans[N];
vector<pair<int,int> > v[N];
vector<int> w,iv[N];
void work(int n){
    for(int i=2;i<=n;i++){
        if(!ip[i]){
            p[++cnt]=i;
        }
        for(int j=1;j<=cnt&&i*p[j]<=n;j++){
            ip[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }
}
void dfs(int u){
    for(int i=c[u];i<v[u].size();i++){
        int ver=v[u][i].first,id=v[u][i].second;
        c[u]++;
        if(!id){
            v[u][i].second=1;
            v[ver][iv[u][i]].second=1;
            dfs(ver);
        }
    }
    ans[++cnt]=u;
}
int main(){
    freopen("array.in","r",stdin);
    freopen("array.out","w",stdout); 
    work(N-5);
    for(int i=1;i<=2000;i++){
        a[i]=i*(i+1)/2+1;
        if(i%2==0) a[i]-=(i/2-1);
    }
    cin>>n;
    int x=lower_bound(a+1,a+2001,n)-a;
    w.clear();
    cnt=0;
    for(int i=1;i<=x;i++){
        v[i].clear();
        iv[i].clear();
        tr[i]=c[i]=0;
        for(int j=1;j<=x;j++){
            if((x%2==0)&&(i>=3)&&(abs(i-j)==1)&&(min(i,j)&1)) continue;
            v[i].push_back(make_pair(j,0));
        }
    }
    for(int i=1;i<=x;i++){
        iv[i].resize(v[i].size());
        for(int j=0;j<v[i].size();j++){
            iv[i][j]=(tr[v[i][j].first]++);
        }
    }
    dfs(1);
    cout<<x<<"\n";
    for(int i=1;i<=n;i++) cout<<p[ans[i]]<<" ";
    cout<<"\n";
    return 0;
}