Codeforces 131 E. Yet Another Task with Queens
問題
nxnのチェス盤にm個のクイーンが置かれている。
クイーンのうち、
他の0個のクイーンの効きにあるような駒の数、
他の1個のクイーンの効きにあるような駒の数、
……
他の8個のクイーンの効きにあるような駒の数
をそれぞれ求めよ。
制約条件
n≦10^5
m≦10^5
方針
効きごとにsetを作って駒を突っ込んで、
それぞれの駒に対して、両隣に駒があるかを見るという強引なことをやったら通った。
ソースコード
set<int> yoko[100000],tate[100000],dia1[200010],dia2[200010]; int n,m,ans[9]; void run() { cin>>n>>m; vi ys,xs; rep(i,m){ int y,x; cin>>y>>x; ys.pb(--y); xs.pb(--x); int d1=y-x+100000,d2=y+x; dia1[d1].insert(x); dia2[d2].insert(x); yoko[y].insert(x); tate[x].insert(y); } rep(i,m){ int cnt=0; set<int>::iterator it; it=yoko[ys[i]].find(xs[i]); if(it!=yoko[ys[i]].begin())cnt++; if(++it!=yoko[ys[i]].end())cnt++; it=tate[xs[i]].find(ys[i]); if(it!=tate[xs[i]].begin())cnt++; if(++it!=tate[xs[i]].end())cnt++; int d1=ys[i]-xs[i]+100000, d2=ys[i]+xs[i]; it=dia1[d1].find(xs[i]); if(it!=dia1[d1].begin())cnt++; if(++it!=dia1[d1].end())cnt++; it=dia2[d2].find(xs[i]); if(it!=dia2[d2].begin())cnt++; if(++it!=dia2[d2].end())cnt++; ans[cnt]++; } rep(i,9)cout<<ans[i]<<(i==8?"\n":" "); }