Codeforces Round #295 Div1 B(Cubes)

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,q2q1的顶元素最大,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

//Hello. I'm Peter.
#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){//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<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){//.. 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<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);
}
波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 本站源码并不保证全部能正常使用,仅供有技术基础的人学习研究,请谨慎下载
8. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » Codeforces Round #295 Div1 B(Cubes)

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡