「AOJ531~540」の編集履歴(バックアップ)一覧に戻る
#include<stdio.h> #include<vector> #include<set> #include <algorithm> struct point{ int x1,x2,y,inOut; bool operator<(const point p)const{ if(y!=p.y)return y<p.y; return inOut>p.inOut; } void set(int xi,int xi2,int yi,int inOuti){ x1=xi; x2=xi2; y=yi; inOut=inOuti; } }; std::vector<bool> moveOKs; void connectSearch(std::vector<std::set<int> >& con,int now){ std::set<int>::iterator it=con[now].begin(); moveOKs[now]=false; while(it!=con[now].end()){ if(moveOKs[(*it)]==true)connectSearch(con,(*it)); it++; } } void setData(int w,int h){ int n; point p; scanf("%d",&n); int x1,y1,x2,y2; std::vector<point> points; std::set<int> xs; moveOKs.clear(); for(int i=0;i<n;i++){ scanf("%d %d %d %d",&x1,&y1,&x2,&y2); p.set(x1,x2,y1,1); points.push_back(p); p.set(x1,x2,y2,-1); points.push_back(p); xs.insert(x1); xs.insert(x2); } xs.insert(0); p.set(0,w,0,1); points.push_back(p); p.set(0,w,0,-1); points.push_back(p); p.set(0,w,h,1); points.push_back(p); std::sort(points.begin(),points.end()); std::set<int>::iterator it=xs.begin(); int nowX,colorCount=0,size; int inOutCount,now,old,turn=0; std::vector<int> yMemo[2]; std::vector<int> yNoMemo[2]; std::vector<std::set<int> > connect; std::set<int> dammySet; while(it!=xs.end()){ nowX=(*it); inOutCount=0; now=turn%2; old=(turn+1)%2; turn++; yMemo[now].clear(); yNoMemo[now].clear(); size=points.size()-1; for(int i=0;i<size;i++){ if(nowX<points[i].x1 || points[i].x2<=nowX)continue; //printf("(%d %d %d %d %d) \n",i,points[i].x1,points[i].x2,points[i].y,points[i].inOut); inOutCount+=points[i].inOut; if(inOutCount==0){ yMemo[now].push_back(points[i ].y); int tempy=points[i].y; while(tempy==points[i].y || nowX<points[i].x1 || points[i].x2<=nowX){ i++; if(points[i].x1<=nowX && nowX<points[i].x2){ inOutCount+=points[i].inOut; //printf("(%d %d %d %d %d) \n",i,points[i].x1,points[i].x2,points[i].y,points[i].inOut); } } yMemo[now].push_back(points[i].y); yNoMemo[now].push_back(-1); } } //printf("\n%d\n",yMemo[now].size()); if(yMemo[now].empty()){ it++; continue; } /* for(int i=0;i<yMemo[now].size();i+=2){ printf("(%d %d)",yMemo[now][i],yMemo[now][i+1]); } printf("\n"); */ size=yMemo[now].size(); unsigned int oldP=0,nowP=0; int y1,y2,y3,y4; while(oldP<yMemo[old].size() && nowP<yMemo[now].size()){ y1=yMemo[old][oldP ]; y2=yMemo[old][oldP+1]; y3=yMemo[now][nowP ]; y4=yMemo[now][nowP+1]; if(y2<=y3){ oldP+=2; }else if(y1>=y4){ if(yNoMemo[now][nowP/2]==-1){ yNoMemo[now][nowP/2]=colorCount; connect.push_back(dammySet); colorCount++; moveOKs.push_back(true); } nowP+=2; }else{ if(yNoMemo[now][nowP/2]==-1){ yNoMemo[now][nowP/2]=yNoMemo[old][oldP/2]; }else{ connect[yNoMemo[now][nowP/2]].insert(yNoMemo[old][oldP/2]); connect[yNoMemo[old][oldP/2]].insert(yNoMemo[now][nowP/2]); } if(y2>y4){ nowP+=2; }else if(y2<y4){ oldP+=2; }else{ nowP+=2; oldP+=2; } } } for(unsigned int i=nowP;i<yMemo[now].size();i+=2){ if(yNoMemo[now][i/2]==-1){ yNoMemo[now][i/2]=colorCount; connect.push_back(dammySet); colorCount++; moveOKs.push_back(true); } } it++; } int sum=0; for(unsigned int i=0;i<moveOKs.size();i++){ if(moveOKs[i]==true){ sum++; connectSearch(connect,i); } } printf("%d\n",sum); } int main(){ int w,h; while(1){ scanf("%d %d",&w,&h); if(w==0 && h==0) break; setData(w,h); } }
#include<stdio.h> int main(){ int h,m,s,h2,m2,s2; for(int i=0;i<3;i++){ scanf("%d %d %d %d %d %d",&h,&m,&s,&h2,&m2,&s2); int wtime=(h2-h)*3600+(m2-m)*60+(s2-s); printf("%d %d %d\n",wtime/3600,(wtime%3600)/60,wtime%60); } }
#include<stdio.h> #include <algorithm> int main(){ int s[20]; for(int i=0;i<20;i++)scanf("%d",&s[i]); std::sort(s,s+10); std::sort(s+10,s+20); printf("%d %d\n",s[9]+s[8]+s[7],s[19]+s[18]+s[17]); }
#include<stdio.h> int dellSearch(int nowP,int col[10002]){ int upP=nowP,downP=nowP,count=4; int nowColor,ansUp=nowP+1,ansDown=nowP; while(count>3){ count=0; if(upP==downP)count=-1; if(col[upP]==-1 || col[downP]==-1) break; nowColor=col[upP]; while(col[upP]==nowColor){ upP++; count++; } while(col[downP]==nowColor){ downP--; count++; } if(count>3){ ansUp=upP; ansDown=downP; } } return ansUp-ansDown-1; } void setData(int n){ int col[10002]; for(int i=1;i<=n;i++){ scanf("%d",&col[i]); } col[0]=col[n+1]=-1;//番兵 int temp,t,ans=0; for(int i=1;i<=n;i++){ temp=col[i]; for(int k=1;k<4;k++){ col[i]=k; t=dellSearch(i,col); ans=ans>t?ans:t; } col[i]=temp; } printf("%d\n",n-ans); } int main(){ int n; while(1){ scanf("%d",&n); if(n==0) break; setData(n); } }
#include<stdio.h> int w,h,ans; int dxs[4]={1,0,-1,0}; int dys[4]={0,1,0,-1}; int map[91][91]; void saiki(int x,int y,int deep){ if(x<0 || w<=x || y<0 || h<=y) return; if(map[y][x]==0)return; map[y][x]=0; ans=ans>deep?ans:deep; int nx,ny; for(int i=0;i<4;i++){ nx=x+dxs[i]; ny=y+dys[i]; saiki(nx,ny,deep+1); } map[y][x]=1; } void setData(){ ans=0; for(int y=0;y<h;y++){ for(int x=0;x<w;x++){ scanf("%d",&map[y][x]); } } for(int y=0;y<h;y++){ for(int x=0;x<w;x++){ saiki(x,y,1); } } printf("%d\n",ans); } int main(){ while(1){ scanf("%d %d",&w,&h); if(w==0 && h==0) break; setData(); } }
#include<stdio.h> #include<vector> struct card{ int top,last; }; void setCard(int n){ int m,p,q,r,x,y; std::vector<card> cards; std::vector<card> yama1,yama2,yama3; std::vector<card>::iterator it; card c,c1,c2; scanf("%d",&m); scanf("%d %d %d",&p,&q,&r); for(int i=0;i<m;i++){ scanf("%d %d",&x,&y); if(cards.empty()==true){ c.last=n; c.top=y+1; cards.push_back(c); c.last=y; c.top=x+1; cards.push_back(c); c.last=x; c.top=1; cards.push_back(c); }else{ int count=0; it=cards.begin(); yama1.clear(); yama2.clear(); yama3.clear(); while(count<x){ count+=(*it).last-(*it).top+1; yama1.push_back(*it); it++; } if(count>x){ c1=yama1.back(); c=yama1.back(); c2=yama1.back(); yama1.pop_back(); c1.last=c1.last-(count-x); yama1.push_back(c1); c.top=c1.last+1; if(count>y){ c.last=c.top+y-x-1; yama2.push_back(c); c1.top=c.last+1; c1.last=c2.last; yama3.push_back(c1); yama3.insert(yama3.end(),it,cards.end()); }else if(count==y){ c.last=c2.last; yama2.push_back(c); yama3.insert(yama3.end(),it,cards.end()); }else{ c.last=c2.last; yama2.push_back(c); while(count<y){ count+=(*it).last-(*it).top+1; yama2.push_back(*it); it++; } if(count>y){ c=yama2.back(); c1=yama2.back(); yama2.pop_back(); c.last=c.last-(count-y); yama2.push_back(c); c1.top=c.last+1; yama3.push_back(c1); yama3.insert(yama3.end(),it,cards.end()); }else{ yama3.insert(yama3.end(),it,cards.end()); } } }else if(x==count){ while(y>count){ count+=(*it).last-(*it).top+1; yama2.push_back(*it); it++; } if(y<count){ c=yama2.back(); c1=yama2.back(); yama2.pop_back(); c.last=c.last-(count-y); yama2.push_back(c); c1.top=c.last+1; yama3.push_back(c1); yama3.insert(yama3.end(),it,cards.end()); }else{ yama3.insert(yama3.end(),it,cards.end()); } } cards.clear(); cards.insert(cards.end(),yama3.begin(),yama3.end()); cards.insert(cards.end(),yama2.begin(),yama2.end()); cards.insert(cards.end(),yama1.begin(),yama1.end()); } } it=cards.begin(); int count=0,ans=0,tl,ts; //ここまでは多分完璧 bool first=true; //printf("<ts tl count ans>\n"); while(it!=cards.end()){ count+=(*it).last-(*it).top+1; if(p<=count){ if(first==true){ first=false; ts=(*it).last-(count-p); }else{ ts=(*it).top; } if(count<=q){ tl=(*it).last; }else{ tl=(*it).last-(count-q); //printf("a"); } if(r<ts){ ans+=0; }else if(ts<=r && r<=tl){ ans+=r-ts+1; }else if(ts<=r && tl<=r){ ans+=tl-ts+1; } //printf("<%d %d %d %d>",ts,tl,count,ans); } it++; if(q<=count) break; } printf("%d\n",ans); } int main(){ int n; scanf("%d",&n); while(n!=0){ setCard(n); scanf("%d",&n); } }
#include<stdio.h> void search(int n){ const int max=1000001; int ans=0,size,mode=0,count=0; char text[max]; scanf("%d %s",&size,text); for(int i=0;i<size;i++){ if(mode==0 && text[i]=='I'){ count++; mode=1; }else if(mode==1 && text[i]=='O'){ mode=0; }else{ ans+=count-n>0?count-n:0; count=mode=text[i]=='I'?1:0; } } ans+=count-n>0?count-n:0; printf("%d\n",ans); } int main(){ int n; while(1){ scanf("%d",&n); if(n==0) break; search(n); } }
#include<stdio.h> #include<set> void setData(int d){ int n,m,p; scanf("%d %d",&n,&m); std::set<int> shops; shops.insert(0); shops.insert(d); for(int i=1;i<n;i++){ scanf("%d",&p); shops.insert(p); } std::set<int>::iterator it1,it2; int d1,d2,ans=0; for(int i=0;i<m;i++){ scanf("%d",&p); it1=shops.upper_bound(p); it2=it1; it1--; d1=p-(*it1); d2=(*it2)-p; ans+=d1>d2?d2:d1; } printf("%d\n",ans); } int main(){ int d; while(1){ scanf("%d",&d); if(d==0) break; setData(d); } }
#include<stdio.h> #include<set> #include <algorithm> #include<string.h> #include<vector> struct bar{ int x,y; bool operator<(const bar b)const{ if(y!=b.y)return y<b.y; return x<b.x; } }; int calc(int dps[1002],int k){ int ans=0; for(int i=1;i<=k;i++){ ans+=dps[i]; } return ans; } int memo[1002][1002];//n段目の棒を削除した場合n段目までのあみだは同じということを利用して結果を再利用する bool setData(){ int points[1002];//得点 int n,m,h,k; scanf("%d %d %d %d",&n,&m,&h,&k); if(n+m+h+k==0) return false; for(int i=0;i<n;i++){ scanf("%d",&points[i+1]);//縦棒には1番から番号が付いている } bar b; std::set<bar> bars; for(int i=0;i<m;i++){ scanf("%d %d",&b.x,&b.y); bars.insert(b); } int nowRow[1002]; //まずは1本も削除しない場合を計算する。 for(int x=1;x<=n;x++){ nowRow[x]=memo[0][x]=x; } std::set<bar>::iterator it=bars.begin(); int nowY=(*it).y; while(it!=bars.end()){ if(nowY!=(*it).y){ memcpy(memo[nowY]+1,nowRow+1,4*n); nowY=(*it).y; }else{ std::swap(nowRow[(*it).x],nowRow[(*it).x+1]); it++; } } int downPoints[1002]; memcpy(memo[nowY]+1,nowRow+1,4*n); for(int x=1;x<=n;x++){ downPoints[nowRow[x]]=points[x]; } it=bars.begin(); int temp,r,l,ans; ans=calc(downPoints,k); while(it!=bars.end()){ r=memo[(*it).y][(*it).x ]; l=memo[(*it).y][(*it).x+1]; if(r>k && l>k){ it++; continue; } std::swap(downPoints[r],downPoints[l]); temp=calc(downPoints,k); ans=ans>temp?temp:ans; std::swap(downPoints[r],downPoints[l]); it++; } printf("%d\n",ans); return true; } int main(){ while(setData()){ } }