[CF 521B] Cubes

這題寫的好卡阿@@......一個小時多才過=ㄦ=

作法：

可以想到就是維護「現在還有哪些方塊可以取」，所以上面沒有任何方塊的方塊可以被取，但我一開始想的時候漏了「這個方塊上面有方塊，但別人有幫他支撐所以可以拿掉」的情形，害我慌了一陣子(?)，所以對每個方塊要記錄上面和下面根他相鄰的有誰，還有每次拿掉一個方塊的時候，第一個是如果它底下有方塊沒有支撐東西了，就可以把它加進去，另外一個可能是被拿掉的方塊上面的方塊剩下一個支撐物了，所以他的左右鄰居可能會變成不能拿，必須要砍掉。

另外我一開始又看錯題目，以為是越大越好，原來是要一次取最大一次取最小OAO

code :

#include<bits/stdc++.h>
#define pii pair<int,int>
#define F first
#define S second
#define mkp(x,y) make_pair(x,y)
#define LL long long
#define MOD 1000000009
using namespace std;
const int maxn=100000+10 ;
 
map<pii,int> mp ;
vector<int> v[maxn],v2[maxn] ;
int x[maxn],y[maxn],deg[maxn] ;
int dx[]={-1,0,1} , dy[]={1,1,1} , dx2[]={-2,-1,1,2} ;
set<int> s1 ;
set<int,greater<int> > s2 ;
bool done[maxn] ;
 
int cal(int id)
{
    int ret=0 ;
    for(auto i : v[id]) if(!done[i]) ret++ ;
    return ret ;
}
 
bool check(int x)
{
    if(!deg[x]) return 1 ;
    for(auto i : v2[x]) if(!done[i] && cal(i)==1) return 0 ;
    return 1 ;
}
 
void erase(int u)
{
    done[u]=1 ;
    for(auto i : v[u]) deg[i]-- ;
    s1.erase(u) ; s2.erase(u) ;
    mp.erase(mkp(x[u],y[u])) ;
 
    for(int i=0;i<4;i++)
    {
        auto it1=mp.find(mkp(x[u]+dx2[i],y[u])) ;
        if(it1!=mp.end())
        {
            if(check(it1->S)) continue ;
            auto it2=s1.find(it1->S) ;
            if(it2!=s1.end())
                s1.erase(it1->S) ,
                s2.erase(it1->S) ;
        }
    }
}
 
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&x[i],&y[i]) ;
        mp[mkp(x[i],y[i])]=i ;
    }
 
    for(int i=0;i<n;i++) for(int j=0;j<3;j++)
    {
        int nx=x[i]+dx[j] , ny=y[i]+dy[j] ;
        auto it=mp.find(mkp(nx,ny)) ;
        if(it!=mp.end())
            v[it->S].push_back(i) ,
            v2[i].push_back(it->S) ,
            deg[i]++ ;
    }
 
    LL ans=0LL ;
    for(int i=0;i<n;i++) if(check(i))
        s1.insert(i) , s2.insert(i) ;
    for(int type=0;!s1.empty();type^=1)
    {
        int u= type==0 ? *s2.begin() : *s1.begin() ;
        erase(u) ;
        ans=(ans*((LL)n)+u)%MOD ;
        for(auto i : v[u]) if(!done[i] && check(i))
            s1.insert(i) , s2.insert(i) ;
    }
    printf("%I64d\n",ans) ;
}