Codeforces Round 1012 (Div. 2)

AB略

C

没看懂题意，翻译的问题。t=0代表这个人必须找一个没有人的桌子且座位离他最近，t=1代表这个人只要找一个空座位就可以了。一个桌子四个座位，t=0肯定会坐左下角的那个。首先建立两个小根堆q1代表左下角的座位，q2代表一个桌子的左下角被坐后同桌子上其他的座位。当t=0或者此时被坐左下角的座位所在桌子的其他座位已经被坐完了或者q2的距离最近的座位的距离小于q1的距离最近的座位时，坐q1，否则坐q2。q1可以先预处理开，而q2只有当q1被坐后才能解锁。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int T,n,a[50010];
void init()
{
}
struct node
{
    int dis,x,y;
    friend bool operator>(const node& a,const node& b)
    {
        if(a.dis==b.dis)
        {
            if(a.x==b.x) return a.y>b.y;
            return a.x>b.x;
        }
        return a.dis>b.dis;
    }
    friend bool operator<(const node& a,const node& b)
    {
        if(a.dis==b.dis)
        {
            if(a.x==b.x) return a.y<b.y;
            return a.x<b.x;
        }
        return a.dis<b.dis;
    }
};

void solve()
{   
    cin>>n;
    init();
    priority_queue<node,vector<node>,greater<node> > q1;
    priority_queue<node,vector<node>,greater<node> > q2;
    int m=2*sqrt(n);
    for(int i=0;i<=m;i++)
    for(int j=0;j<=m;j++)
    {
        q1.push({3*i+3*j+2,3*i+1,3*j+1});
    }
    for(int i=1;i<=n;i++)
    {
        int t;
        cin>>t;
        if(!q2.size()||t==0||q2.top()>q1.top())
        {
            node p=q1.top();
            q1.pop();
            cout<<p.x<<" "<<p.y<<endl;
            q2.push({p.dis+1,p.x,p.y+1});
            q2.push({p.dis+1,p.x+1,p.y});
            q2.push({p.dis+4,p.x+1,p.y+1});
        }
        else
        {
            cout<<q2.top().x<<" "<<q2.top().y<<endl;
            q2.pop();
        }
    }
}
signed main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
    while(T--) solve();
}

D

构造题，看起来很复杂，其实要求很宽松。首先一个数如果是质数，那么把这个数排在第一位，后面依次排-1，+1，-1，+1，可以使得每隔两个c都是质数，而如果这个质数在n/3~n/3*2的范围内，这个质数最多可以达到n/3个，恰好符合题意

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int T,n,v[N],prime[N],cnt,x;
void init()
{
}
void solve()
{   
    cin>>n;
    if(n==2) {cout<<2<<" "<<1<<endl; return;}
    for(int i=n/3;i<=n/3*2;i++)
    if(!v[i]) {x=i;break;}
    cout<<x<<" ";
    for(int i=1;i<=min(x-1,n-x);i++)
    {
        cout<<x-i<<" "<<x+i<<" ";
    }
    if(x-1<n-x)
    {
        for(int i=2*x;i<=n;i++)
        cout<<i<<" ";
    }
    else
    {
        for(int i=1;i<=x-(n-x)-1;i++)
        cout<<i<<" ";
    }
    cout<<endl;
}
signed main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    v[1]=1;
    for(int i=2;i<=N;i++)
    {
        if(v[i]) continue;
        prime[++cnt]=i;
        for(int j=i;j<=N/i;j++) v[i*j]=1;
    }
	cin>>T;
    while(T--) solve();
}