程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> Codeforces Round #295 Div1 B（Cubes）

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_queueqbig;
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];
        pairp=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;
                pairp=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);
        pairp=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;
    vectorres;
    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);
            pairp=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];
                pairp=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);
            pairp=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];
                pairp=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);
}