結果
問題 | No.202 1円玉投げ |
ユーザー | hirokazu1020 |
提出日時 | 2015-05-15 05:33:49 |
言語 | C++11 (gcc 11.4.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,506 bytes |
コンパイル時間 | 578 ms |
コンパイル使用メモリ | 78,132 KB |
実行使用メモリ | 38,284 KB |
最終ジャッジ日時 | 2023-08-23 22:50:18 |
合計ジャッジ時間 | 4,641 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 76 ms
11,236 KB |
testcase_01 | AC | 219 ms
38,284 KB |
testcase_02 | AC | 5 ms
8,560 KB |
testcase_03 | AC | 5 ms
8,820 KB |
testcase_04 | AC | 6 ms
8,572 KB |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | AC | 68 ms
13,148 KB |
testcase_17 | AC | 64 ms
11,232 KB |
testcase_18 | AC | 64 ms
11,088 KB |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | AC | 5 ms
8,844 KB |
testcase_23 | AC | 5 ms
8,560 KB |
testcase_24 | AC | 6 ms
8,520 KB |
testcase_25 | AC | 5 ms
8,632 KB |
testcase_26 | AC | 6 ms
9,080 KB |
testcase_27 | AC | 6 ms
9,132 KB |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | AC | 6 ms
8,924 KB |
testcase_31 | AC | 5 ms
8,516 KB |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | AC | 5 ms
8,544 KB |
testcase_35 | AC | 63 ms
11,252 KB |
testcase_36 | AC | 69 ms
11,184 KB |
testcase_37 | WA | - |
testcase_38 | AC | 70 ms
11,288 KB |
testcase_39 | AC | 6 ms
8,732 KB |
testcase_40 | WA | - |
ソースコード
#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=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[20011]; 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-10);!hit&&a<=y+10;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; }