Codeforces Round #295 Div1 B（Cubes） - c++编程基础

Problem

这里写图片描述

Limits

TimeLimit(ms):3000

MemoryLimit(MB):256

M∈[1,105]

Xi∈[?109,109]

Yi∈[0,109]

Look up Original Problem From here

Solution

一个点可取，当且仅当，把它取了之后，上面的点不会失去平衡而掉下来。

开两个优先队列 q1,q2 。 q1 的顶元素最大， q2 的顶元素最小，起初把所有可取的点都放入 q1,q2 ，然后，轮流从 q1,q2 取点，如果访问过了就取下一个，取出点后，判断这个点是否可取，如果不可取则取下一个…每次取出的点，判断 (Xi?1,Yi?1),(Xi,Yi?1),(Xi+1,Yi?1) 这三个点是否可取，如果可取，则加入 q1,q2 。这样就可以得到M进制数。

Complexity

TimeComplexity:O(M×log2M)

MemoryComplexity:O(M)

My Code

//Hello. I'm Peter.
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #include
                
                  #include
                 
                   #include
                   using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef unsigned int uin; #define peter cout<<"i am peter"<
                   
                     b; i--) #define repin(i, a, b) for (int i = a; i <= b; i++) #define depin(i, a, b) for (int i = a; i >= b; i--) #define pi 3.1415926535898 #define eps 1e-9 #define MOD 1000000007 #define MAXN #define N 100100 #define M priority_queue
                    
                     qbig; priority_queue
                     
                      , greater
                      
                        >qsmall; int m; bool vis[N]; map
                       
                        ,int>mapit; struct Point{ int x,y; }poi[N]; int dx[6]={-1,0,1,-1,0,1}; int dy[6]={-1,-1,-1,1,1,1}; const ll mod=1e9 + 9; bool can_move(Point p0){ rep(i,3,6){ Point p1; p1.x=p0.x+dx[i]; p1.y=p0.y+dy[i]; pair
                        
                         p=make_pair(p1.x,p1.y); if(mapit.find(p)!=mapit.end()){ int t1=mapit[p]; if(vis[t1]) continue; bool ok=false; rep(j,0,3){ Point p2; p2.x=p1.x+dx[j]; p2.y=p1.y+dy[j]; if(p2.x==p0.x && p2.y==p0.y) continue; pair
                         
                          p=make_pair(p2.x,p2.y); if(mapit.find(p)!=mapit.end()){ int t1=mapit[p]; if(vis[t1]) continue; ok=true; break; } } if(!ok) return false; } } return true; } int main(){ scanf("%d",&m); rep(i,0,m){ int x,y; scanf("%d %d",&x,&y); pair
                          
                           p=make_pair(x,y); mapit[p]=i; poi[i].x=x,poi[i].y=y; vis[i]=false; } rep(i,0,m){ if(can_move(poi[i])){ qbig.push(i); qsmall.push(i); } } int turn=-1; vector
                           
                            res; res.clear(); while(1){ int now=0; turn=(turn+1)%2; if(turn==0){//Vasya big while(!qbig.empty()){ now=qbig.top(); if(vis[now]){ qbig.pop(); continue; } else if(!can_move(poi[now])){ qbig.pop(); continue; } else break; } if(qbig.empty()) break; qbig.pop(); vis[now]=true; res.pb(now); pair
                            
                             p=make_pair(poi[now].x,poi[now].y); mapit.erase(p); rep(i,0,3){ int x=poi[now].x+dx[i]; int y=poi[now].y+dy[i]; pair
                             
                              p=make_pair(x,y); if(mapit.find(p)!=mapit.end()){ int t1=mapit[p]; if(vis[t1]) continue; if(can_move(poi[t1])){ qbig.push(t1); qsmall.push(t1); } } } } else if(turn==1){//.. small while(!qsmall.empty()){ now=qsmall.top(); if(vis[now]){ qsmall.pop(); continue; } else if(!can_move(poi[now])){ qsmall.pop(); continue; } else break; } if(qsmall.empty()) break; qsmall.pop(); vis[now]=true; res.pb(now); pair
                              
                               p=make_pair(poi[now].x,poi[now].y); mapit.erase(p); rep(i,0,3){ int x=poi[now].x+dx[i]; int y=poi[now].y+dy[i]; pair
                               
                                p=make_pair(x,y); if(mapit.find(p)!=mapit.end()){ int t1=mapit[p]; if(vis[t1]) continue; if(can_move(poi[t1])){ qbig.push(t1); qsmall.push(t1); } } } } } int len=gsize(res); ll m1=1,ans=0; depin(i,len-1,0){ ans=(ans+((res[i]*m1)%mod))%mod; m1=(m1*m)%mod; } printf("%lld\n",ans); }