結果
問題 | No.202 1円玉投げ |
ユーザー | hirokazu1020 |
提出日時 | 2015-05-15 05:36:15 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 261 ms / 5,000 ms |
コード長 | 3,505 bytes |
コンパイル時間 | 837 ms |
コンパイル使用メモリ | 84,020 KB |
実行使用メモリ | 37,928 KB |
最終ジャッジ日時 | 2024-12-22 09:08:45 |
合計ジャッジ時間 | 4,856 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include<sstream>#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<string>#include<vector>#include<set>#include<map>#include<queue>#include<numeric>#include<functional>#include<algorithm>using namespace std;#define INF (1<<29)#define rep(i,n) for(int i=0;i<(int)(n);i++)#define all(v) v.begin(),v.end()#define uniq(v) v.erase(unique(all(v)),v.end())#define indexOf(v,x) (find(all(v),x)-v.begin())int highest_pop(unsigned int b){#ifdef __GNUC__return 31-__builtin_clz(b);#elseint res=0;for(int i=4;i>=0;i--){int shift=1<<i;if(b>>shift){b>>=shift;res|=shift;}}return res;#endif}template<int U=30>class Set{unsigned int summary;Set<U-5> *ch[1<<5];static int low_bits(unsigned int a){return a&((1<<U-5)-1);}static int high_bits(unsigned int a){return a>>(U-5);}static int index(unsigned int high,unsigned int low){return high<<U-5|low;}public:Set():summary(0){for(int i=0;i<(1<<5);i++)ch[i]=NULL;}~Set(){clear();}void clear(){summary=0;for(int i=0;i<(1<<5);i++){if(ch[i])delete ch[i];ch[i]=NULL;}}void insert(int v){int high=high_bits(v);summary|=1<<high;if(!ch[high])ch[high]=new Set<U-5>();ch[high]->insert(low_bits(v));}bool erase(int v){int high=high_bits(v);if(!ch[high])return true;if(!ch[high]->erase(low_bits(v))){delete ch[high];ch[high]=NULL;return summary&=~(1<<high);}return true;}int nextvalue(int v)const{int high=high_bits(v);int low=low_bits(v);int a;if(ch[high] && (a=ch[high]->nextvalue(low))!=-1){return index(high,a);}else{high=summary&~((1<<high)-1)&~(1<<high);if(!high)return -1;high=highest_pop(high&-high);return index(high,ch[high]->min());}}int prevvalue(int v)const{int high=high_bits(v);int low=low_bits(v);int a;if(ch[high] && (a=ch[high]->prevvalue(low))!=-1){return index(high,a);}else{high=summary&((1<<high)-1);if(!high)return -1;high=highest_pop(high);return index(high,ch[high]->max());}}int min()const{if(!summary)return -1;int high=highest_pop(summary&-summary);return index(high,ch[high]->min());}int max()const{if(!summary)return -1;int high=highest_pop(summary);return index(high,ch[high]->max());}bool member(int v)const{int high=high_bits(v);return ch[high] && ch[high]->member(low_bits(v));}};template<>class Set<5>{unsigned int summary;public:Set():summary(0){}void clear(){summary=0;}void insert(int v){summary|=1<<v;}bool erase(int v){return summary&=~(1<<v);}int nextvalue(int v)const{int a=summary&~((1<<v)-1)&~(1<<v);if(!a)return -1;return highest_pop(a&-a);}int prevvalue(int v)const{int a=summary&((1<<v)-1);if(!a)return -1;return highest_pop(a);}int min()const{if(!summary)return -1;return highest_pop(summary&-summary);}int max()const{if(!summary)return -1;return highest_pop(summary);}bool member(int v)const{return summary>>v&1;}};Set<15> xset[20021];int main(){int n,ans=0;cin>>n;rep(i,n){bool hit=false;int x,y;cin>>x>>y;for(int a=max(0,y-20);!hit&&a<y+20;a++){int b;b=xset[a].nextvalue(x);if(b!=-1&&(a-y)*(a-y)+(b-x)*(b-x)<20*20)hit=true;b=xset[a].prevvalue(x+1);if(b!=-1&&(a-y)*(a-y)+(b-x)*(b-x)<20*20)hit=true;}if(!hit){xset[y].insert(x);ans++;}}cout<<ans<<endl;return 0;}