12054

myee · 2025-04-08 18:29:57 · 题解

前言

出题人题解。

如你所见这是在你清食堂吃饭的真实经历……

原本是命题会上发现缺一个模拟，于是我就掏出了一个这个，大家一致通过后就选上了。

应该算是近几年 THUPC 最简单的几道模拟之一了？

本题的 CF ver. 是一个弱化版本，可以进一步优化到不带 \log。

思路

观察到性质：当座位同样可选时，优先级是确定的。我们不妨先对此进行排序。这部分使用 BFS 或者数学方法 d(x,y)=x+y+2[x\bmod3=y\bmod3=2] 容易做到线性。

那么我们的目标每次就是要找到一个编号尽可能小的符合某种要求的可选座位，或者翻转某个座位的状态。

观察到找到可选座位的过程只可能涉及 O(\sqrt q) 坐标范围内的桌子（是一个 3000 左右的上界），我们不妨把坐标范围不在指定范围内的翻转操作单独用一个哈希表来处理。

这样为了维护第一种操作，我们只用考虑 O(q) 级别的信息了。

注意到，“找到编号尽可能小”本身是一个常用堆维护的结构。而这里我们每次翻转一个座位的状态时，对应的四个格子的可行性都可能发生改变，于是有相应的插入或者删除操作。

也即，我们需要用可删堆维护每种忍受度的可行编号集合，具体可以使用 set 或者两个 priority_queue 来快速实现。

总复杂度 O(n\log n)。

Code

为了写的尽可能简单一点，std 没有加一些优化。如果加了的话应该能快一倍？

最终 std 不到 2kb。

// キミは泣いた後 笑えるはずだから って言ったんだ
// 仆らの旅 忘れたりしないよ
// 失くさないよう魔法かけて さよならを伝えない
// 歩き出すよ またいつか

#include <bits/stdc++.h>

using uint = unsigned;
using bol = bool;

const uint W=10001;
const uint T=3031;
const uint R=2000000;

bol G[T*T];
uint Id[T*T],Ord[R+5];

uint Nxt(uint p,uint o)
{
    uint x=p/T,y=p%T;
    if(o&1)y=y/3*3+3-y%3;
    if(o&2)x=x/3*3+3-x%3;
    return x*T+y;
}

std::set<uint>P[3],Q;

bol flip(uint x,uint y)
{
    if(x>=T||y>=T)
    {
        if(Q.count(x*W+y))return Q.erase(x*W+y),0;
        return Q.insert(x*W+y),1;
    }
    uint p[4]={0,0,0,0};for(uint i=0;i<4;i++)p[i]=Nxt(x*T+y,i);
    if(G[p[0]])
    {
        G[p[0]]=0;
        for(uint o=0;o<4;o++)if(~Id[p[o]])
        {
            if(!G[p[o]]&&!o)P[2].erase(Id[p[o]]);
            if(!G[p[o]]||!G[p[o^1]]||!G[p[o^2]])P[1].erase(Id[p[o]]);
            P[0].erase(Id[p[o]]);
        }
        return 1;
    }
    else
    {
        G[p[0]]=1;
        for(uint o=0;o<4;o++)if(~Id[p[o]])
        {
            if(G[p[o]])
            {
                if(!o)P[2].insert(Id[p[o]]);
                if(G[p[o^1]]&&G[p[o^2]])
                {
                    if(o!=3)P[1].insert(Id[p[o]]);
                    if(G[p[o^3]])P[0].insert(Id[p[o]]);
                }
            }
        }
        return 0;
    }
}

int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    freopen("QAQ.out","w",stdout);
#endif
    G[0]=true;
    for(auto&s:Id)s=-1;
    for(uint tp=0,c=1;tp<R;)
    {
        static uint Now[50005],Next[50005];
        uint t=0;
        for(uint j=0;j<c;j++)
        {
            uint p=Now[j];
            if(p%T&&!G[p-1])G[p-1]=true,Next[t++]=p-1;
            if(p/T&&!G[p-T])G[p-T]=true,Next[t++]=p-T;
            if(p%T+1<T&&!G[p+1])G[p+1]=true,Next[t++]=p+1;
            if(p/T+1<T&&!G[p+T])G[p+T]=true,Next[t++]=p+T;
        }
        std::sort(Next,Next+t),c=0;
        for(uint j=0;j<t;j++)if(Next[j]/T%3&&Next[j]%T%3){if(tp<R)Ord[Id[Next[j]]=tp++]=Next[j];}else Now[c++]=Next[j];
    }
    for(auto&s:G)s=1;
    for(uint i=0;i<R;i++)P[0].insert(i);
    P[1]=P[2]=P[0];
    uint q;scanf("%u",&q);
    while(q--)
    {
        uint t;scanf("%u",&t);
        if(t==1)
        {
            scanf("%u",&t);t=Ord[*P[t].begin()];
            uint x=t/T,y=t%T;printf("%u %u\n",x,y),flip(x,y);
        }
        else
        {
            uint x,y;scanf("%u%u",&x,&y);puts(flip(x,y)?"in":"out");
        }
    }
    return 0;
}