JOI合宿問題
合宿問題でジャッジでACをとった問題でUPするだけの価値のあるもののソースを張っていきます。
Fish(この間のせた)
#include<stdio.h> #include<vector> #include<algorithm> #include<set> using namespace std; typedef long long ll; typedef pair<ll,ll>pii; typedef pair<ll,pii>pi3; int main() { int num; scanf("%d",&num); vector<int>va,vb,vc; for(int i=0;i<num;i++) { int za; char zb; scanf("%d %c",&za,&zb); if(zb=='R') { va.push_back(za); } if(zb=='G') { vb.push_back(za); } if(zb=='B') { vc.push_back(za); } } sort(va.begin(),va.end()); sort(vb.begin(),vb.end()); sort(vc.begin(),vc.end()); vector<pi3>vec; for(int i=0;i<va.size();i++) { int lowa=lower_bound(va.begin(),va.end(),va[i])-va.begin(); int uppa=upper_bound(va.begin(),va.end(),va[i]*2-1)-va.begin(); int lowb=lower_bound(vb.begin(),vb.end(),va[i])-vb.begin(); int uppb=upper_bound(vb.begin(),vb.end(),va[i]*2-1)-vb.begin(); int lowc=lower_bound(vc.begin(),vc.end(),va[i])-vc.begin(); int uppc=upper_bound(vc.begin(),vc.end(),va[i]*2-1)-vc.begin(); vec.push_back(make_pair(uppa-lowa+1,make_pair(uppb-lowb+1,uppc-lowc+1))); } for(int i=0;i<vb.size();i++) { int lowa=lower_bound(va.begin(),va.end(),vb[i])-va.begin(); int uppa=upper_bound(va.begin(),va.end(),vb[i]*2-1)-va.begin(); int lowb=lower_bound(vb.begin(),vb.end(),vb[i])-vb.begin(); int uppb=upper_bound(vb.begin(),vb.end(),vb[i]*2-1)-vb.begin(); int lowc=lower_bound(vc.begin(),vc.end(),vb[i])-vc.begin(); int uppc=upper_bound(vc.begin(),vc.end(),vb[i]*2-1)-vc.begin(); vec.push_back(make_pair(uppa-lowa+1,make_pair(uppb-lowb+1,uppc-lowc+1))); } for(int i=0;i<vc.size();i++) { int lowa=lower_bound(va.begin(),va.end(),vc[i])-va.begin(); int uppa=upper_bound(va.begin(),va.end(),vc[i]*2-1)-va.begin(); int lowb=lower_bound(vb.begin(),vb.end(),vc[i])-vb.begin(); int uppb=upper_bound(vb.begin(),vb.end(),vc[i]*2-1)-vb.begin(); int lowc=lower_bound(vc.begin(),vc.end(),vc[i])-vc.begin(); int uppc=upper_bound(vc.begin(),vc.end(),vc[i]*2-1)-vc.begin(); vec.push_back(make_pair(uppa-lowa+1,make_pair(uppb-lowb+1,uppc-lowc+1))); } sort(vec.begin(),vec.end()); reverse(vec.begin(),vec.end()); set<pii>se; se.insert(make_pair(0,2000000000)); se.insert(make_pair(2000000000,0)); ll ans=0; ll men=0; for(int i=0;i<num;i++) { set<pii>::iterator it=se.lower_bound(vec[i].second); pii zan=*it; if(vec[i].second.first>zan.first||vec[i].second.second>zan.second) { for(;;) { it--; zan=*it; if(vec[i].second.first>=zan.first&&vec[i].second.second>=zan.second) { it--; pii zan2=*it; it++; it++; pii zan3=*it; it--; men-=(zan.first-zan2.first)*(zan.second-zan3.second); se.erase(it++); } else { break; } } it=se.lower_bound(vec[i].second); pii zan3=*it; it--; pii zan2=*it; men+=(vec[i].second.first-zan2.first)*(vec[i].second.second-zan3.second); se.insert(vec[i].second); } if(i==num-1) { ans+=men*vec[i].first; } else { ans+=men*(vec[i].first-vec[i+1].first); } } printf("%lld\n",ans-1); }
JOI flag(実装だいぶ適当)
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; #define mp(A,B) make_pair(A,B) #define mt(A,B,C) mp(mp(A,B),C) #define mq(A,B,C,D) mp(mp(A,B),mp(C,D)) typedef pair<int,int>pii; typedef pair<pii,int>pi3; typedef pair<pii,pii>pi4; pi4 calc(vector<pi3>vec,int lx,int ly,int hen) { if(vec.empty()) { return mq(0,0,0,0); } if(hen==1) { if(vec[0].second==0) { return mq(0,1,1,0); } if(vec[0].second==1) { return mq(1,0,1,0); } if(vec[0].second==2) { return mq(1,1,0,0); } } vector<pi3>v11,v12,v21,v22; int n1=0,n2=0,n3=0; for(int i=0;i<vec.size();i++) { if(vec[i].first.first<lx+hen/2) { if(vec[i].first.second<ly+hen/2) { v11.push_back(vec[i]); } else { v12.push_back(vec[i]); } } else { if(vec[i].first.second<ly+hen/2) { v21.push_back(vec[i]); } else { v22.push_back(vec[i]); } } if(vec[i].second==0) { n2++; n3++; } if(vec[i].second==1) { n1++; n3++; } if(vec[i].second==2) { n1++; n2++; } } vector<pi4>r; r.resize(4); r[0]=calc(v11,lx,ly,hen/2); r[1]=calc(v12,lx,ly+hen/2,hen/2); r[2]=calc(v21,lx+hen/2,ly,hen/2); r[3]=calc(v22,lx+hen/2,ly+hen/2,hen/2); vector<int>per; for(int i=0;i<4;i++) { per.push_back(i); } int mini=1<<30; for(;;) { mini=min(mini,r[per[0]].first.first+r[per[1]].first.second+r[per[2]].second.first+r[per[3]].second.second); if(!next_permutation(per.begin(),per.end())) { break; } } return mq(n1,n2,n3,mini); } int main() { int num,hen; scanf("%d%d",&hen,&num); vector<pi3>vec; for(int i=0;i<num;i++) { int za,zb; char zc; scanf("%d%d %c",&za,&zb,&zc); za--; zb--; if(zc=='J') { vec.push_back(mt(za,zb,0)); } if(zc=='O') { vec.push_back(mt(za,zb,1)); } if(zc=='I') { vec.push_back(mt(za,zb,2)); } } printf("%d\n",calc(vec,0,0,1<<hen).second.second); }
Lines 有理数でやってるので誤差とは無縁 そのかわり0除算が怖いので分岐が多くなってる
#include<stdio.h> #include<vector> #include<algorithm> #include<stdlib.h> using namespace std; typedef long long ll; typedef pair<ll,ll>pii; typedef pair<pii,ll>pi3; typedef pair<pii,pii>pi4; ll gcd(ll a,ll b) { if(a==0) { return b; } if(b==0) { return a; } for(;;) { if(a<b) { swap(a,b); } a%=b; if(a==0) { return b; } } } pi3 toline(ll a,ll b,ll c,ll d) { if(d<b) { swap(a,c); swap(b,d); } if(d==b) { return make_pair(make_pair(0,1),d); } if(a==c) { return make_pair(make_pair(1,0),a); } if(a*d==b*c) { ll g=gcd(abs(d-b),abs(a-c)); return make_pair(make_pair((d-b)/g,(a-c)/g),0); } ll g=gcd(gcd(abs(d-b),abs(a-c)),abs(a*d-b*c)); return make_pair(make_pair((d-b)/g,(a-c)/g),(a*d-b*c)/g); } pi4 cross(pi3 a,pi3 b) { pii x=make_pair((a.second*b.first.second-b.second*a.first.second),(a.first.first*b.first.second-a.first.second*b.first.first)); if(x.second<0) { x.first=-x.first; x.second=-x.second; } ll g=gcd(abs(x.first),abs(x.second)); x.first/=g; x.second/=g; swap(a.first.second,a.first.first); swap(b.first.second,b.first.first); pii y=make_pair((a.second*b.first.second-b.second*a.first.second),(a.first.first*b.first.second-a.first.second*b.first.first)); if(y.second<0) { y.first=-y.first; y.second=-y.second; } g=gcd(abs(y.first),abs(y.second)); y.first/=g; y.second/=g; return make_pair(x,y); } int count(vector<pi4>a) { sort(a.begin(),a.end()); pi4 now=make_pair(make_pair(523453423434LL,5876567587LL),make_pair(78957826239LL,356238963LL)); int ret=0; for(int i=0;i<a.size();i++) { if(now!=a[i]) { now=a[i]; ret++; } } return ret; } int main() { int num; scanf("%d",&num); vector<pi3>vec; for(int i=0;i<num;i++) { ll za,zb,zc,zd; scanf("%lld%lld%lld%lld",&za,&zb,&zc,&zd); vec.push_back(toline(za,zb,zc,zd)); pi3 zan=toline(za,zb,zc,zd); } pi3 now=make_pair(make_pair(0,0),0); vector<pi3>zv; sort(vec.begin(),vec.end()); for(int i=0;i<num;i++) { if(now!=vec[i]) { now=vec[i]; zv.push_back(now); //printf("%lld x+%lld y=%lld\n",now.first.first,now.first.second,now.second); } } vec=zv; vector<pi4>point; int ans=1; for(int i=0;i<vec.size();i++) { vector<pi4>zp; for(int j=0;j<vec.size();j++) { //printf("%d %d\n",i,j); if(i==j) { continue; } if(vec[i].first.first*vec[j].first.second!=vec[i].first.second*vec[j].first.first) { pi4 z=cross(vec[i],vec[j]); //printf("(%lld / %lld) (%lld / %lld)\n",z.first.first,z.first.second,z.second.first,z.second.second); zp.push_back(z); point.push_back(z); } } ans+=count(zp)+1; } ans-=count(point); printf("%d\n",ans); }
Flu setでごりごりしたらTLEしたのでおとなしくバケット組んだ(そっちのほうが実装軽い)
#include<stdio.h> #include<vector> #include<algorithm> #include<set> #include<queue> using namespace std; typedef pair<int,int>pii; typedef pair<pii,int>pi3; vector<int>pat[100000]; int flag[100000]; vector<pi3>brk[42][42]; int main() { int cit,nic,dis,gen; scanf("%d%d%d%d",&cit,&nic,&dis,&gen); vector<pi3>vec; for(int i=0;i<cit;i++) { int za,zb; scanf("%d%d",&za,&zb); vec.push_back(make_pair(make_pair(za,zb),i)); brk[za/25+1][zb/25+1].push_back(make_pair(make_pair(za,zb),i)); } int pt=0; for(int i=0;i<cit;i++) { for(int j=-1;j<=1;j++) { for(int k=-1;k<=1;k++) { vector<pi3>v=brk[vec[i].first.first/25+1+j][vec[i].first.second/25+1+k]; for(int p=0;p<v.size();p++) { pii zan=v[p].first; if((zan.first-vec[i].first.first)*(zan.first-vec[i].first.first)+(zan.second-vec[i].first.second)*(zan.second-vec[i].first.second)<=dis*dis) { pat[i].push_back(v[p].second); pat[v[p].second].push_back(i); } } } } } fill(flag,flag+cit,-1); queue<pii>que; que.push(make_pair(0,0)); for(;;) { if(que.empty()) { break; } pii zan=que.front(); que.pop(); if(flag[zan.first]!=-1) { continue; } flag[zan.first]=zan.second; for(int i=0;i<pat[zan.first].size();i++) { if(flag[pat[zan.first][i]]==-1) { que.push(make_pair(pat[zan.first][i],zan.second+1)); } } } int ret=0; for(int i=0;i<cit;i++) { if(max(0,gen-nic+1)<=flag[i]&&flag[i]<=gen) { ret++; } } printf("%d\n",ret); }
Typhoon BITやるだけ
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; int bit[262145]; void add(int a,int b) { for(;;) { if(a>=262144) { break; } bit[a]+=b; a+=a&-a; } } int sum(int a) { int ret=0; for(;;) { if(a==0) { break; } ret+=bit[a]; a-=a&-a; } return ret; } #define mp(A,B) make_pair(A,B) #define mq(A,B,C,D) mp(mp(A,B),mp(C,D)) typedef pair<int,int>pii; typedef pair<pii,pii>pi4; int ans[100000]; int main() { int num,query,chi; scanf("%d%d%d",&num,&query,&chi); vector<pi4>vec; vector<int>uni; for(int i=0;i<num;i++) { int za,zb; scanf("%d%d",&za,&zb); uni.push_back(za-1); uni.push_back(zb); vec.push_back(mq(i+1,0,za,zb)); } for(int j=0;j<num;j++) { int za,zb,zc; scanf("%d%d%d",&za,&zb,&zc); vec.push_back(mq(zb-1,1,za,j*2)); vec.push_back(mq(zc,1,za,j*2+1)); } sort(vec.begin(),vec.end()); sort(uni.begin(),uni.end()); vector<int>zuni; int now=-100000000; for(int i=0;i<uni.size();i++) { if(now!=uni[i]) { zuni.push_back(uni[i]); now=uni[i]; } } uni=zuni;/* for(int i=0;i<uni.size();i++) { printf("%d ",uni[i]); } printf("\n");*/ for(int i=0;i<vec.size();i++) {/* for(int p=0;p<uni.size()+1;p++) { printf("%d ",sum(p+1)); } printf("\n"); printf("%d %d %d %d\n",vec[i].first.first,vec[i].first.second,vec[i].second.first,vec[i].second.second);*/ if(vec[i].first.second==0) { int low1=lower_bound(uni.begin(),uni.end(),vec[i].second.first-1)-uni.begin(); int low2=lower_bound(uni.begin(),uni.end(),vec[i].second.second)-uni.begin(); add(low1+2,1); add(low2+2,-1); } else { int low=lower_bound(uni.begin(),uni.end(),vec[i].second.first)-uni.begin(); if(vec[i].second.second%2==0) { ans[vec[i].second.second/2]-=sum(low+1); } else { ans[vec[i].second.second/2]+=sum(low+1); } } } for(int i=0;i<query;i++) { printf("%d\n",ans[i]); } }
Ruins 簡単なDPだけど点が線の上にあるかの判定がきれいにいかない
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; typedef pair<int,int>pii; bool han(pii a,pii b,pii c) { if(b.first<a.first) { swap(a,b); } if(c.second*(b.first-a.first)>(b.second-a.second)*c.first-a.first*b.second+a.second*b.first) { return true; } else { return false; } } int dp[2][128][128][128]; int maxis[2][128][128]; int main() { int num; scanf("%d",&num); vector<pii>vec; for(int i=0;i<num;i++) { int za,zb; scanf("%d%d",&za,&zb); vec.push_back(make_pair(za,zb)); } sort(vec.begin(),vec.end());/* for(int i=0;i<num;i++) { printf(" %d %d\n",vec[i].first,vec[i].second); }*/ for(int i=0;i<num;i++) { for(int j=i+1;j<num;j++) { dp[0][i][i][j]=1; dp[1][i][i][j]=1; } }/* for(int i=0;i<num;i++) { for(int j=i+1;j<num;j++) { for(int k=j+1;k<num;k++) { printf("%d %d %d %d\n",i,j,k,int(han(vec[i],vec[j],vec[k]))); } } }*/ for(int i=0;i<num;i++) { for(int j=i;j<num;j++) { for(int k=j+1;k<num;k++) { for(int l=k+1;l<num;l++) { if(han(vec[j],vec[k],vec[l])&&dp[0][i][j][k]!=0) { dp[0][i][k][l]=max(dp[0][i][k][l],dp[0][i][j][k]+1); } if((!han(vec[j],vec[k],vec[l]))&&dp[1][i][j][k]!=0) { dp[1][i][k][l]=max(dp[1][i][k][l],dp[1][i][j][k]+1); } } } } }/* for(int i=0;i<num;i++) { for(int j=i+1;j<num;j++) { printf("debug:%d %d %d %d\n",i,j,dp[0][0][i][j],dp[1][0][i][j]); } }*/ int maxi=0; for(int i=0;i<num;i++) { for(int j=i;j<num;j++) { for(int k=i;k<j;k++) { maxis[0][i][j]=max(maxis[0][i][j],dp[0][i][k][j]); maxis[1][i][j]=max(maxis[1][i][j],dp[1][i][k][j]); } maxi=max(maxi,maxis[0][i][j]+maxis[1][i][j]); //printf("%d %d %d %d\n",i,j,maxis[0][i][j],maxis[1][i][j]); } } printf("%d\n",maxi); }
Regions 簡単
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; typedef pair<int,int>pii; vector<pii>pat[30000]; vector<pii>ko[30000]; bool flag[30000]; void dfs(int node) { if(flag[node]) { return; } flag[node]=true; for(int i=0;i<pat[node].size();i++) { if(!flag[pat[node][i].first]) { ko[node].push_back(pat[node][i]); dfs(pat[node][i].first); } } } int ret; int calc(int node,int med) { vector<int>vec; for(int i=0;i<ko[node].size();i++) { vec.push_back(calc(ko[node][i].first,med)+ko[node][i].second); } sort(vec.begin(),vec.end()); if(vec.empty()) { return 0; } if(vec.size()==1) { if(vec[0]<=med) { return vec[0]; } else { ret++; return 0; } } if(vec[vec.size()-2]+vec[vec.size()-1]<=med) { return vec[vec.size()-1]; } else { for(int i=0;i<vec.size()-1;i++) { if(vec[i]+vec[i+1]>med) { ret+=vec.size()-i-1; return vec[i]; } } } } int main() { int cit,gen; scanf("%d%d",&cit,&gen); for(int i=0;i<cit-1;i++) { int za,zb,zc; scanf("%d%d%d",&za,&zb,&zc); za--; zb--; pat[za].push_back(make_pair(zb,zc)); pat[zb].push_back(make_pair(za,zc)); } fill(flag,flag+cit,false); dfs(0); int beg=0,end=3000000; for(;;) { int med=(beg+end)/2; ret=0; calc(0,med); ret++; if(ret>gen) { beg=med+1; } else { end=med; } if(beg==end) { printf("%d\n",beg); return 0; } } }
DNA synthesizer ローリングハッシュ(想定解はTrieらしいがlogつけても間に合う)
#include<stdio.h> #include<vector> #include<algorithm> #include<set> #include<string> #include<iostream> using namespace std; typedef long long ll; ll mot=1000000007; vector<ll>vec[21]; int poi[150000]; bool han(ll hash,int lon) { return lower_bound(vec[lon].begin(),vec[lon].end(),hash)!=upper_bound(vec[lon].begin(),vec[lon].end(),hash); } int main() { int num; scanf("%d",&num); string str; cin>>str; for(int i=0;i<num;i++) { string zan; cin>>zan; ll hash=0; for(int j=0;j<zan.size();j++) { hash*=mot; hash+=zan[j]; } vec[zan.size()].push_back(hash); } for(int i=0;i<21;i++) { sort(vec[i].begin(),vec[i].end()); } for(int i=1;i<=min(20,int(str.size()));i++) { ll hash=0; ll jou=1; for(int j=0;j<i;j++) { hash*=mot; hash+=str[j]; jou*=mot; } if(han(hash,i)) { poi[0]=max(poi[0],i-1); } for(int j=i;j<str.size();j++) { hash*=mot; hash+=str[j]; hash-=jou*str[j-i]; if(han(hash,i)) { poi[j-i+1]=max(poi[j-i+1],j); } } } if(str.size()==1) { printf("1\n"); return 0; } int ret=0; int now=0; for(int i=1;i<str.size();i++) { poi[i]=max(poi[i],poi[i-1]); } for(;;) { if(now==str.size()-1) { break; } now=poi[now]; ret++; } printf("%d\n",ret); }
Deciphering こういうちょっとした発想ゲー好き
#include<stdio.h> #include<vector> #include<algorithm> #include<string> #include<iostream> using namespace std; vector<int>moj[26]; bool map[26][26]; int dp[300000]; int mod=10000000; int main() { int num; scanf("%d",&num); string str; for(int i=0;i<num;i++) { char zan; scanf(" %c",&zan); str.push_back(zan); } for(int i=0;i<str.size();i++) { if(moj[str[i]-'A'].empty()) { dp[i]=1; } moj[str[i]-'A'].push_back(i); } for(int i=0;i<26;i++) { reverse(moj[i].begin(),moj[i].end()); } int kin; scanf("%d",&kin); for(int i=0;i<26;i++) { for(int j=0;j<26;j++) { map[i][j]=true; } } for(int i=0;i<kin;i++) { char za,zb; scanf(" %c %c",&za,&zb); map[za-'A'][zb-'A']=false; } int sum=0; for(int i=0;i<num;i++) { moj[str[i]-'A'].pop_back(); for(int j=0;j<26;j++) { if(map[str[i]-'A'][j]&&(moj[j].size()!=0)) { dp[moj[j][moj[j].size()-1]]+=dp[i]; dp[moj[j][moj[j].size()-1]]%=mod; } } sum+=dp[i]; sum%=mod; } printf("%d\n",sum); }
Distribution オーダーもっと悪くても間に合うらしいけどlog解思いついたのでわざとlogでやっている。爆速
#include<stdio.h> #include<vector> #include<algorithm> #include<set> using namespace std; typedef pair<int,int>pii; set<int>ko[10000]; int par[10000]; int cost[10000]; bool flag[10000]; int main() { int num,dis; scanf("%d%d",&num,&dis); int sum=0; for(int i=0;i<num;i++) { int za,zb; scanf("%d%d",&za,&zb); za--; cost[i]=zb; par[i]=za; sum+=zb; if(za!=-1) { ko[za].insert(i); } else { par[i]=0; } } set<pii>se; fill(flag,flag+num,true); int siz=0; for(int i=0;i<num;i++) { if(ko[i].empty()&&flag[i]) { int nowcost=cost[i]; int now=par[i]; int bef=i; for(;;) { if(ko[now].size()!=1||now==0) { ko[now].erase(bef); par[i]=now; ko[now].insert(i); break; } flag[now]=false; nowcost+=cost[now]; bef=par[bef]; now=par[now]; } cost[i]=nowcost; se.insert(make_pair(nowcost,i)); siz++; } } for(int p=0;p<siz-dis;p++) { set<pii>::iterator it=se.begin(); pii zan=*it; se.erase(it); sum-=zan.first; ko[par[zan.second]].erase(zan.second); if(ko[par[zan.second]].size()==1&&par[zan.second]!=0) { set<int>::iterator it2=ko[par[zan.second]].begin(); int zan2=*it2; if(ko[zan2].empty()) { se.erase(make_pair(cost[zan2],zan2)); int bef=zan2; int now=par[zan2]; int nowcost=cost[zan2]; for(;;) { if(ko[now].size()!=1) { ko[now].erase(bef); par[zan2]=now; ko[now].insert(zan2); break; } bef=par[bef]; nowcost+=cost[now]; now=par[now]; } se.insert(make_pair(nowcost,zan2)); cost[zan2]=nowcost; } } } printf("%d\n",sum); }
Territory 同じようなコード何回も書くの防ぐのどうすればいいんだろう
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; typedef pair<int,int>pii; typedef pair<pii,int>pi3; typedef long long ll; int main() { vector<pi3>vec; int nx=0,ny=0; for(;;) { char zan; scanf(" %c",&zan); if(zan=='Q') { break; } if(zan=='N') { vec.push_back(make_pair(make_pair(nx,ny),0)); vec.push_back(make_pair(make_pair(nx-1,ny),2)); nx--; } if(zan=='W') { vec.push_back(make_pair(make_pair(nx,ny),1)); vec.push_back(make_pair(make_pair(nx,ny-1),3)); ny--; } if(zan=='S') { vec.push_back(make_pair(make_pair(nx,ny),2)); vec.push_back(make_pair(make_pair(nx+1,ny),0)); nx++; } if(zan=='E') { vec.push_back(make_pair(make_pair(nx,ny),3)); vec.push_back(make_pair(make_pair(nx,ny+1),1)); ny++; } } sort(vec.begin(),vec.end()); if(vec.empty()) { printf("0\n"); return 0; }/* for(int i=0;i<vec.size();i++) { printf("debug:%d %d %d\n",vec[i].first.first,vec[i].first.second,vec[i].second); }*/ nx=vec[0].first.first; ny=vec[0].first.second; int nh=vec[0].second; bool han=false; vector<pii>ans; for(;;) { //printf("%d %d %d\n",nx,ny,nh); if(make_pair(make_pair(nx,ny),nh)==vec[0]) { if(han) { break; } han=true; } if(nh==0) { ans.push_back(make_pair(nx-1,ny)); } if(nh==2) { ans.push_back(make_pair(nx,ny)); } if(nh==0) { if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx-1,ny),3))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx-1,ny),3))) { nx--; nh=3; continue; } if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx-1,ny),0))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx-1,ny),0))) { nx--; nh=0; continue; } if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx-1,ny),1))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx-1,ny),1))) { nx--; nh=1; continue; } if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx-1,ny),2))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx-1,ny),2))) { nx--; nh=2; continue; } } if(nh==1) { if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny-1),0))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny-1),0))) { ny--; nh=0; continue; } if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny-1),1))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny-1),1))) { ny--; nh=1; continue; } if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny-1),2))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny-1),2))) { ny--; nh=2; continue; } if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny-1),3))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny-1),3))) { ny--; nh=3; continue; } } if(nh==2) { if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx+1,ny),1))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx+1,ny),1))) { nx++; nh=1; continue; } if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx+1,ny),2))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx+1,ny),2))) { nx++; nh=2; continue; } if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx+1,ny),3))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx+1,ny),3))) { nx++; nh=3; continue; } if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx+1,ny),0))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx+1,ny),0))) { nx++; nh=0; continue; } } if(nh==3) { if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny+1),2))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny+1),2))) { ny++; nh=2; continue; } if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny+1),3))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny+1),3))) { ny++; nh=3; continue; } if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny+1),0))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny+1),0))) { ny++; nh=0; continue; } if(lower_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny+1),1))!=upper_bound(vec.begin(),vec.end(),make_pair(make_pair(nx,ny+1),1))) { ny++; nh=1; continue; } } } sort(ans.begin(),ans.end()); ll sum=0; int now=-100000000; bool gk=false;/* for(int i=0;i<ans.size();i++) { printf("%d %d\n",ans[i].first,ans[i].second); }*/ for(int i=0;i<ans.size();i++) { if(now!=ans[i].first) { gk=true; now=ans[i].first; } else { if(gk) { sum+=ans[i].second-ans[i-1].second; gk=false; } else { gk=true; } } } printf("%lld\n",sum); }
Guess them all にぶたん。最初の0hitの例の構成は乱数で適当にやる(1/eくらいの確率で0hitなので常勝)
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; int hai[100]; int main() { int num; scanf("%d",&num); vector<int>zer; for(;;) { for(int i=0;i<num;i++) { int zan=(rand()%num)+1; printf("%d\n",zan); zer.push_back(zan); } fflush(stdout); int ret; scanf("%d",&ret); if(ret==0) { break; } if(ret==num) { return 0; } zer.clear(); } vector<int>jun; int rui[100]; int ans[100]; for(int i=0;i<num;i++) { rui[i]=i; } for(int i=0;i<num;i++) { int beg=0,end=num-i-1; for(;;) { int med=(beg+end)/2; for(int j=0;j<num;j++) { if(j<=rui[med]) { printf("%d\n",i+1); } else { printf("%d\n",zer[j]); } } fflush(stdout); int ret; scanf("%d",&ret); if(ret==0) { beg=med+1; } else { end=med; } if(ret==num) { return 0; } if(beg==end) { ans[rui[beg]]=i+1; for(int k=beg;k<num-i;k++) { rui[k]=rui[k+1]; } break; } } } for(int i=0;i<num;i++) { printf("%d\n",ans[i]); } fflush(stdout); }
Shiritori coutを消すゲーム
#include<stdio.h> #include<vector> #include<algorithm> #include<string> #include<iostream> using namespace std; vector<string>map[100][100]; int ein[100]; int eout[100]; vector<int>topo; bool flag[100]; int ban[100]; vector<int>to[100]; void dfs(int node) { if(flag[node]) { return; } flag[node]=true; for(int i=0;i<100;i++) { if(!flag[i]&&map[node][i].size()!=0) { dfs(i); } } topo.push_back(node); } void rdfs(int node,int b) { if(flag[node]) { return; } flag[node]=true; for(int i=0;i<100;i++) { if(!flag[i]&&map[i][node].size()!=0) { rdfs(i,b); } } ban[node]=b; to[b].push_back(node); } void scc() { topo.clear(); for(int i=0;i<100;i++) { to[i].clear(); } fill(flag,flag+100,false); for(int i=0;i<100;i++) { if(!flag[i]&&(ein[i]!=0||eout[i]!=0)) { dfs(i); } } fill(flag,flag+100,false); int now=0; for(int i=topo.size()-1;i>=0;i--) { if(!flag[topo[i]]) { rdfs(topo[i],now); now++; } } } int main() { int num; scanf("%d",&num); for(int i=0;i<num;i++) { string zan; zan.resize(10); for(int j=0;j<10;j++) { scanf(" %c",&zan[j]); } ein[(zan[8]-'0')*10+(zan[9]-'0')]++; eout[(zan[0]-'0')*10+(zan[1]-'0')]++; map[(zan[0]-'0')*10+(zan[1]-'0')][(zan[8]-'0')*10+(zan[9]-'0')].push_back(zan); } int pl=0,mi=0; int st=-1; for(int i=0;i<100;i++) { if(ein[i]!=eout[i]) { if(ein[i]+1==eout[i]) { pl++; st=i; } else { if(ein[i]==eout[i]+1) { mi++; } else { pl+=2; mi+=2; } } } } if(pl==0&&mi==0) { for(int i=0;i<100;i++) { if(eout[i]!=0) { st=i; break; } } } fill(flag,flag+100,false); dfs(st); for(int i=0;i<100;i++) { if((ein[i]!=0||eout[i]!=0)&&!flag[i]) { pl=2; mi=2; } } if(pl>=2||mi>=2) { printf("impossible\n"); return 0; } for(int i=0;i<100;i++) { for(int j=0;j<100;j++) { sort(map[i][j].begin(),map[i][j].end()); reverse(map[i][j].begin(),map[i][j].end()); } } scc(); bool fl=false; for(int i=0;i<num;i++) { if(ein[st]==0) { string mini="9"; mini[0]++; int nn=-1; for(int j=0;j<100;j++) { if(map[st][j].size()!=0) { if(mini>map[st][j][map[st][j].size()-1]) { mini=map[st][j][map[st][j].size()-1]; nn=j; } } } string zan=map[st][nn][map[st][nn].size()-1]; cout<<zan<<endl; map[st][nn].pop_back(); if(map[st][nn].empty()) { scc(); } eout[st]--; ein[nn]--; st=nn; } else { string mini="9"; mini[0]++; int nn=-1; for(int j=0;j<100;j++) { if(ban[j]==ban[st]&&map[st][j].size()!=0) { if(mini>map[st][j][map[st][j].size()-1]) { mini=map[st][j][map[st][j].size()-1]; nn=j; } } } string zan=map[st][nn][map[st][nn].size()-1]; for(int p=0;p<10;p++) { printf("%c",zan[p]); } printf("\n"); map[st][nn].pop_back(); if(map[st][nn].empty()) { scc(); } eout[st]--; ein[nn]--; st=nn; } } }
Apples 動的segtree実装簡単だった
#include<stdio.h> #include<vector> #include<algorithm> #include<set> using namespace std; typedef long long ll; #define SIZE 1073741824LL class segtree { public: int seg[7000000]; int flag[7000000]; int lko[7000000]; int rko[7000000]; int segpt; void init() { fill(lko,lko+7000000,-1); fill(rko,rko+7000000,-1); segpt=1; } void makenode(int node,int s) { if(s==0) { lko[node]=segpt; segpt++; } else { rko[node]=segpt; segpt++; } } void update(ll beg,ll end,int node,ll lb,ll ub,int num) { if(ub<beg||end<lb) { return; } if(beg<=lb&&ub<=end) { seg[node]+=num; flag[node]+=num; return; } if(lko[node]==-1) { makenode(node,0); } if(rko[node]==-1) { makenode(node,1); } if(flag[node]) { flag[lko[node]]+=flag[node]; flag[rko[node]]+=flag[node]; seg[lko[node]]+=flag[node]; seg[rko[node]]+=flag[node]; flag[node]=0; } update(beg,end,lko[node],lb,(lb+ub)/2,num); update(beg,end,rko[node],(lb+ub)/2+1,ub,num); seg[node]=max(seg[lko[node]],seg[rko[node]]); return; } ll get(int node,ll lb,ll ub,ll num) { if(lb==ub) { return lb; } if(lko[node]==-1) { makenode(node,0); } if(rko[node]==-1) { makenode(node,1); } if(flag[node]) { flag[lko[node]]+=flag[node]; flag[rko[node]]+=flag[node]; seg[lko[node]]+=flag[node]; seg[rko[node]]+=flag[node]; flag[node]=0; } if(seg[rko[node]]>=num) { return get(rko[node],(lb+ub)/2+1,ub,num); } else { return get(lko[node],lb,(lb+ub)/2,num); } } }; segtree tree; int main() { int query; ll dif; scanf("%d%lld",&query,&dif); multiset<ll>se; tree.init(); for(int p=0;p<query;p++) { char za; ll zb; scanf(" %c",&za); if(za=='E') { break; } scanf("%lld",&zb); if(za=='A') { tree.update(zb,min(SIZE-1,zb+dif),0,0LL,SIZE-1LL,1); se.insert(zb); } else { if(tree.seg[0]<zb) { printf("NO\n"); fflush(stdout); } else { ll ret=tree.get(0,0LL,SIZE-1,zb); multiset<ll>::iterator it=se.upper_bound(ret); it--; vector<ll>ans; for(int i=0;i<zb;i++) { ans.push_back(*it); tree.update(*it,min(SIZE-1,*it+dif),0,0LL,SIZE-1,-1); se.erase(it--); } reverse(ans.begin(),ans.end()); for(int i=0;i<ans.size();i++) { if(i!=0) { printf(" "); } printf("%lld",ans[i]); } printf("\n"); fflush(stdout); } } } }
Fortune telling 閉区間でもできます
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; typedef long long ll; class segtree { public: ll seg[524288]; int flip[524288]; ll sper[524288]; void init(vector<int>vec) { for(int i=0;i<524288;i++) { seg[i]=0; flip[i]=0; } for(int i=262144;i<262144+vec.size()-1;i++) { sper[i]=vec[i-262144+1]-vec[i-262144]; } for(int i=262144+vec.size();i<524288;i++) { sper[i]=0; } for(int i=262143;i>0;i--) { sper[i]=sper[i*2]+sper[i*2+1]; } } ll update(int beg,int end,int node,int lb,int ub) { if(ub<beg||end<lb) { return seg[node]; } if(beg<=lb&&ub<=end) { flip[node]^=1; return seg[node]=sper[node]-seg[node]; } if(flip[node]) { flip[node*2]^=1; seg[node*2]=sper[node*2]-seg[node*2]; flip[node*2+1]^=1; seg[node*2+1]=sper[node*2+1]-seg[node*2+1]; flip[node]=0; } return seg[node]=update(beg,end,node*2,lb,lb+sper[node*2]-1)+update(beg,end,node*2+1,lb+sper[node*2],ub); } ll get() { return seg[1]; } }; segtree tree; typedef pair<int,int>pii; typedef pair<int,pii>pi3; int main() { int mx,my,query; scanf("%d%d%d",&mx,&my,&query); vector<pi3>vec; vec.push_back(make_pair(0,make_pair(-1,-1))); vector<int>zat; for(int i=0;i<query;i++) { int za,zb,zc,zd; scanf("%d%d%d%d",&za,&zb,&zc,&zd); zc--; zd--; vec.push_back(make_pair(za-1,make_pair(zc,zd))); vec.push_back(make_pair(zb,make_pair(zc,zd))); zat.push_back(zc); zat.push_back(zd+1); } zat.push_back(0); zat.push_back(my); vec.push_back(make_pair(mx,make_pair(2000000000,2000000000))); sort(vec.begin(),vec.end()); sort(zat.begin(),zat.end()); vector<int>zv; int now=-1; for(int i=0;i<zat.size();i++) { if(now!=zat[i]) { zv.push_back(zat[i]); now=zat[i]; } } zat=zv; tree.init(zat); ll ret=0; for(int i=1;i<vec.size();i++) { ret+=tree.get()*(vec[i].first-vec[i-1].first); if(i!=vec.size()-1) { tree.update(vec[i].second.first,vec[i].second.second,1,0,zat[zat.size()-1]); } } ll men=mx; men*=my; printf("%lld\n",men-ret); }
Rotate 4つ持っておいて張り替える
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; char map[4020000]; int down[4020000]; int right[4020000]; int todown[4][1002]; int toright[4][1002]; int main() { int num,query; scanf("%d%d",&num,&query); for(int i=0;i<(num+2)*(num+2);i++) { map[i]=' '; down[i]=i; right[i]=i; } for(int i=1;i<=num;i++) { for(int j=1;j<=num;j++) { char zan; scanf(" %c",&zan); map[i*(num+2)+j]=zan; map[(num+2)*(num+2)+(num+1-j)*(num+2)+i]=zan; map[(num+2)*(num+2)*2+(num+1-i)*(num+2)+(num+1-j)]=zan; map[(num+2)*(num+2)*3+j*(num+2)+(num+1-i)]=zan; } } for(int i=0;i<4;i++) { for(int j=0;j<num+1;j++) { for(int k=0;k<num+2;k++) { down[i*(num+2)*(num+2)+j*(num+2)+k]=i*(num+2)*(num+2)+(j+1)*(num+2)+k; right[i*(num+2)*(num+2)+k*(num+2)+j]=i*(num+2)*(num+2)+k*(num+2)+(j+1); } } } for(int i=0;i<4;i++) { for(int j=0;j<num+2;j++) { todown[i][j]=i*(num+2)*(num+2)+j; toright[i][j]=i*(num+2)*(num+2)+j*(num+2); } } for(int i=0;i<query;i++) { int za,zb,zc; scanf("%d%d%d",&za,&zb,&zc); int now[8]; now[0]=now[4]=toright[0][za]; now[1]=now[5]=toright[1][num+1-zb-zc+1]; now[2]=now[6]=toright[2][num+1-za-zc+1]; now[3]=now[7]=toright[3][zb]; for(int j=0;j<zb-1;j++) { now[0]=right[now[0]]; } for(int j=0;j<za-1;j++) { now[1]=right[now[1]]; } for(int j=0;j<num+1-zb-zc+1-1;j++) { now[2]=right[now[2]]; } for(int j=0;j<num+1-za-zc+1-1;j++) { now[3]=right[now[3]]; } for(int j=0;j<zb+zc-1;j++) { now[4]=right[now[4]]; } for(int j=0;j<za+zc-1;j++) { now[5]=right[now[5]]; } for(int j=0;j<num+1-zb-zc+1+zc-1;j++) { now[6]=right[now[6]]; } for(int j=0;j<num+1-za-zc+1+zc-1;j++) { now[7]=right[now[7]]; } for(int j=0;j<zc;j++) { int t=right[now[0]]; right[now[0]]=right[now[1]]; right[now[1]]=right[now[2]]; right[now[2]]=right[now[3]]; right[now[3]]=t; t=right[now[4]]; right[now[4]]=right[now[7]]; right[now[7]]=right[now[6]]; right[now[6]]=right[now[5]]; right[now[5]]=t; for(int k=0;k<8;k++) { now[k]=down[now[k]]; } } now[0]=now[4]=todown[0][zb]; now[1]=now[5]=todown[1][za]; now[2]=now[6]=todown[2][num+1-zb-zc+1]; now[3]=now[7]=todown[3][num+1-za-zc+1]; for(int j=0;j<za-1;j++) { now[0]=down[now[0]]; } for(int j=0;j<num+1-zb-zc+1-1;j++) { now[1]=down[now[1]]; } for(int j=0;j<num+1-za-zc+1-1;j++) { now[2]=down[now[2]]; } for(int j=0;j<zb-1;j++) { now[3]=down[now[3]]; } for(int j=0;j<za-1+zc;j++) { now[4]=down[now[4]]; } for(int j=0;j<num+1-zb-zc+1-1+zc;j++) { now[5]=down[now[5]]; } for(int j=0;j<num+1-za-zc+1-1+zc;j++) { now[6]=down[now[6]]; } for(int j=0;j<zb-1+zc;j++) { now[7]=down[now[7]]; } for(int j=0;j<zc;j++) { int t=down[now[0]]; down[now[0]]=down[now[1]]; down[now[1]]=down[now[2]]; down[now[2]]=down[now[3]]; down[now[3]]=t; t=down[now[4]]; down[now[4]]=down[now[7]]; down[now[7]]=down[now[6]]; down[now[6]]=down[now[5]]; down[now[5]]=t; for(int k=0;k<8;k++) { now[k]=right[now[k]]; } } } for(int i=1;i<=num;i++) { int now=toright[0][i]; for(int j=1;j<=num;j++) { now=right[now]; printf("%c",map[now]); } printf("\n"); } }
Sokoban 本番でこれ出たら解法わかっても実装できる気がしない
#include<stdio.h> #include<vector> #include<algorithm> #include<queue> using namespace std; typedef long long ll; typedef pair<int,int>pii; typedef pair<pii,int>pi3; int map[1002][1002]; int lowlink[1002][1002]; int topo[1002][1002]; int rev[1002][1002]; pii par[1002][1002]; bool flag[1002][1002]; bool isgo[1002][1002][4]; int kosize[1002][1002][4]; bool bfsflag[1002][1002][4]; int dx[4]={-1,0,1,0}; int dy[4]={0,-1,0,1}; int nowtopo=0,nowrev=0; int dfs(int nodex,int nodey) { if(flag[nodex][nodey]) { return 0; } flag[nodex][nodey]=true; topo[nodex][nodey]=nowtopo++; int ret=0; for(int i=0;i<4;i++) { if(map[nodex+dx[i]][nodey+dy[i]]==0) { if(!flag[nodex+dx[i]][nodey+dy[i]]) { kosize[nodex][nodey][i]=dfs(nodex+dx[i],nodey+dy[i]); isgo[nodex][nodey][i]=true; //printf("%d %d %d %d\n",nodex,nodey,nodex+dx[i],nodey+dy[i]); ret+=kosize[nodex][nodey][i]; par[nodex+dx[i]][nodey+dy[i]]=make_pair(nodex,nodey); } } } rev[nodex][nodey]=nowrev++; return ret+1; } bool isback(int nodex,int nodey,int fo) { return map[nodex+dx[fo]][nodey+dy[fo]]==0&&(!isgo[nodex+dx[fo]][nodey+dy[fo]][(fo+2)%4])&&topo[nodex][nodey]>topo[nodex+dx[fo]][nodey+dy[fo]]; } bool isrevback(int nodex,int nodey,int fo) { return isback(nodex+dx[fo],nodey+dy[fo],(fo+2)%4); } bool islow(int nodex,int nodey,int nodexf,int nodeyf) { return (topo[nodex][nodey]<topo[nodexf][nodeyf]&&rev[nodexf][nodeyf]<rev[nodex][nodey]); } int getlink(int nodex,int nodey,int fo) { if(isgo[nodex][nodey][fo]) { return fo; } for(int i=0;i<4;i++) { if(isgo[nodex][nodey][i]) { if(islow(nodex+dx[i],nodey+dy[i],nodex+dx[fo],nodey+dy[fo])) { return i; } } } return -1; } int calclowlink(int nodex,int nodey) { int minilink=topo[nodex][nodey]; for(int i=0;i<4;i++) { if(isgo[nodex][nodey][i]) { minilink=min(minilink,calclowlink(nodex+dx[i],nodey+dy[i])); } if(isback(nodex,nodey,i)) { minilink=min(minilink,topo[nodex+dx[i]][nodey+dy[i]]); } } return lowlink[nodex][nodey]=minilink; } bool isunited(int nodex,int nodey,int fo1,int fo2) { if(islow(nodex,nodey,nodex+dx[fo2],nodey+dy[fo2])) { swap(fo1,fo2); } if(islow(nodex,nodey,nodex+dx[fo2],nodey+dy[fo2])) { //printf("lowlow\n"); int link1=getlink(nodex,nodey,fo1),link2=getlink(nodex,nodey,fo2); if(link1==link2) { return true; } return lowlink[nodex+dx[link1]][nodey+dy[link1]]<topo[nodex][nodey]&&lowlink[nodex+dx[link2]][nodey+dy[link2]]<topo[nodex][nodey]; } if(islow(nodex,nodey,nodex+dx[fo1],nodey+dy[fo1])) { //printf("lowup\n"); int link=getlink(nodex,nodey,fo1); return lowlink[nodex+dx[link]][nodey+dy[link]]<topo[nodex][nodey]; } //printf("upup\n"); return true; } int getsize(int nodex,int nodey,int fo) { int link=getlink(nodex,nodey,fo); if(link!=-1) { if(bfsflag[nodex][nodey][link]) { return 0; } bfsflag[nodex][nodey][link]=true; return kosize[nodex][nodey][link]; } if(par[nodex][nodey]==make_pair(nodex+dx[fo],nodey+dy[fo])&&(!bfsflag[nodex][nodey][fo])) { int ret=nowtopo-2; for(int i=0;i<4;i++) { ret-=kosize[nodex][nodey][i]; } bfsflag[nodex][nodey][fo]=true; return ret; } return 0; } int main() { int mx,my; scanf("%d%d",&mx,&my); int sx,sy; for(int i=0;i<=mx+1;i++) { for(int j=0;j<=my+1;j++) { map[i][j]=1; flag[i][j]=false; for(int k=0;k<4;k++) { bfsflag[i][j][k]=false; } lowlink[i][j]=1000000000; } } for(int i=0;i<mx;i++) { for(int j=0;j<my;j++) { char zan; scanf(" %c",&zan); if(zan=='.') { map[i+1][j+1]=0; } if(zan=='X') { sx=i+1; sy=j+1; map[i+1][j+1]=0; } } } dfs(sx,sy); calclowlink(sx,sy);/* for(int i=0;i<mx+2;i++) { for(int j=0;j<my+2;j++) { printf("%d ",topo[i][j]); } printf("\n"); } for(int i=0;i<mx+2;i++) { for(int j=0;j<my+2;j++) { printf("%11d",lowlink[i][j]); } printf("\n"); }*/ queue<pi3>que; for(int i=0;i<4;i++) { if(map[sx+dx[i]][sy+dy[i]]==0) { que.push(make_pair(make_pair(sx,sy),i)); } } ll ans=0; for(;;) { if(que.empty()) { break; } pi3 zan=que.front(); que.pop(); if(bfsflag[zan.first.first][zan.first.second][zan.second]) { continue; } //printf("%d %d %d\n",zan.first.first,zan.first.second,zan.second); for(int i=0;i<4;i++) { if(map[zan.first.first+dx[i]][zan.first.second+dy[i]]==0&&map[zan.first.first+dx[zan.second]][zan.first.second+dy[zan.second]]==0) { //printf("%d\n",i); if(isunited(zan.first.first,zan.first.second,i,zan.second)) { if(!bfsflag[zan.first.first][zan.first.second][i]) { if(zan.first!=make_pair(sx,sy)) { ans+=getsize(zan.first.first,zan.first.second,i); } //printf("ok %d\n",ans); } if(map[zan.first.first+2*dx[i]][zan.first.second+2*dy[i]]==0) { que.push(make_pair(make_pair(zan.first.first+dx[i],zan.first.second+dy[i]),i)); } } } } bfsflag[zan.first.first][zan.first.second][zan.second]=true; } printf("%lld\n",ans); }