結果
問題 | No.202 1円玉投げ |
ユーザー | hirokazu1020 |
提出日時 | 2015-05-15 16:20:12 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 263 ms / 5,000 ms |
コード長 | 3,392 bytes |
コンパイル時間 | 576 ms |
コンパイル使用メモリ | 78,284 KB |
実行使用メモリ | 86,320 KB |
最終ジャッジ日時 | 2023-08-23 22:52:01 |
合計ジャッジ時間 | 5,982 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 113 ms
86,016 KB |
testcase_01 | AC | 263 ms
86,104 KB |
testcase_02 | AC | 36 ms
86,096 KB |
testcase_03 | AC | 36 ms
86,020 KB |
testcase_04 | AC | 37 ms
86,076 KB |
testcase_05 | AC | 43 ms
86,168 KB |
testcase_06 | AC | 198 ms
86,024 KB |
testcase_07 | AC | 221 ms
86,080 KB |
testcase_08 | AC | 225 ms
86,312 KB |
testcase_09 | AC | 128 ms
86,164 KB |
testcase_10 | AC | 65 ms
86,104 KB |
testcase_11 | AC | 107 ms
86,204 KB |
testcase_12 | AC | 108 ms
86,020 KB |
testcase_13 | AC | 69 ms
86,072 KB |
testcase_14 | AC | 44 ms
86,036 KB |
testcase_15 | AC | 126 ms
86,104 KB |
testcase_16 | AC | 108 ms
86,108 KB |
testcase_17 | AC | 98 ms
86,024 KB |
testcase_18 | AC | 98 ms
86,044 KB |
testcase_19 | AC | 116 ms
86,180 KB |
testcase_20 | AC | 181 ms
86,076 KB |
testcase_21 | AC | 118 ms
86,028 KB |
testcase_22 | AC | 37 ms
86,204 KB |
testcase_23 | AC | 37 ms
86,136 KB |
testcase_24 | AC | 37 ms
86,180 KB |
testcase_25 | AC | 37 ms
86,072 KB |
testcase_26 | AC | 37 ms
86,036 KB |
testcase_27 | AC | 38 ms
86,028 KB |
testcase_28 | AC | 37 ms
86,136 KB |
testcase_29 | AC | 37 ms
86,044 KB |
testcase_30 | AC | 37 ms
86,068 KB |
testcase_31 | AC | 37 ms
86,068 KB |
testcase_32 | AC | 38 ms
86,024 KB |
testcase_33 | AC | 37 ms
86,220 KB |
testcase_34 | AC | 37 ms
86,320 KB |
testcase_35 | AC | 96 ms
86,292 KB |
testcase_36 | AC | 100 ms
86,012 KB |
testcase_37 | AC | 241 ms
86,036 KB |
testcase_38 | AC | 101 ms
86,068 KB |
testcase_39 | AC | 37 ms
86,200 KB |
testcase_40 | AC | 37 ms
86,040 KB |
ソースコード
#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); #else int 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=20> 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){} ~Set(){} void clear(){ for(int i=0;i<(1<<5);i++) if(summary>>i&1)ch[i].clear(); summary=0; } void insert(int v){ int high=high_bits(v); summary|=1<<high; ch[high].insert(low_bits(v)); } bool erase(int v){ int high=high_bits(v); if(!(summary>>high&1))return true; if(!ch[high].erase(low_bits(v))){ return summary&=~(1<<high); } return true; } int nextvalue(int v)const{ int high=high_bits(v); int low=low_bits(v); int a; if((summary>>high&1) && (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((summary>>high&1) && (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 (summary>>high&1) && 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; }