Problem
Limits
TimeLimit(ms):3000
MemoryLimit(MB):256
M∈[1,105]
Xi∈[?109,109]
Yi∈[0,109]
Look up Original Problem From here
Solution
1个点可取,当且仅当,把它取了以后,上面的点不会失去平衡而掉下来。
开两个优先队列q1,q2。q1的顶元素最大,q2的顶元素最小,起初把所有可取的点都放入q1,q2,然后,轮番从q1,q2取点,如果访问过了就取下1个,取出点后,判断这个点是不是可取,如果不可取则取下1个…每次取出的点,判断(Xi?1,Yi?1),(Xi,Yi?1),(Xi+1,Yi?1)这3个点是不是可取,如果可取,则加入q1,q2。这样就能够得到M进制数。
Complexity
TimeComplexity:O(M×log2M)
MemoryComplexity:O(M)
My Code
#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<cctype>
#include<ctime>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
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"<<endl
#define input freopen("data.txt","r",stdin)
#define randin srand((unsigned int)time(NULL))
#define INT (0x3f3f3f3f)*2
#define LL (0x3f3f3f3f3f3f3f3f)*2
#define gsize(a) (int)a.size()
#define len(a) (int)strlen(a)
#define slen(s) (int)s.length()
#define pb(a) push_back(a)
#define clr(a) memset(a,0,sizeof(a))
#define clr_minus1(a) memset(a,⑴,sizeof(a))
#define clr_INT(a) memset(a,INT,sizeof(a))
#define clr_true(a) memset(a,true,sizeof(a))
#define clr_false(a) memset(a,false,sizeof(a))
#define clr_queue(q) while(!q.empty()) q.pop()
#define clr_stack(s) while(!s.empty()) s.pop()
#define rep(i, a, b) for (int i = a; i < b; i++)
#define dep(i, a, b) for (int i = a; i > 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⑼
#define MOD 1000000007
#define MAXN
#define N 100100
#define M
priority_queue<int>qbig;
priority_queue<int, vector<int>, greater<int> >qsmall;
int m;
bool vis[N];
map<pair<int,int>,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<int,int>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<int,int>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<int,int>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<ll>res;
res.clear();
while(1){
int now=0;
turn=(turn+1)%2;
if(turn==0){
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<int,int>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<int,int>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){
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<int,int>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<int,int>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
",ans);
}