結果
問題 |
No.2368 I love a square root of 2
|
ユーザー |
|
提出日時 | 2023-07-01 03:48:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 36 ms / 2,000 ms |
コード長 | 1,077 bytes |
コンパイル時間 | 786 ms |
コンパイル使用メモリ | 77,904 KB |
実行使用メモリ | 10,644 KB |
最終ジャッジ日時 | 2024-07-07 14:57:12 |
合計ジャッジ時間 | 1,830 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<cassert> using namespace std; const int LIM=2e5; long B[LIM]; long cnt[LIM]; bool f(pair<long,long>p,pair<long,long>q) {//p<q long a=p.first,b=p.second; long c=q.first,d=q.second; if(a-c<0) { if(d-b<0)return (a-c)*(a-c)>2*(d-b)*(d-b); else return true; } else { if(d-b<0)return false; else return (a-c)*(a-c)<2*(d-b)*(d-b); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); B[0]=1; cnt[0]=1; for(int c=1;c<LIM;c++) { long b=B[c-1]-1; long d=(long)c*c; while(2*(b+1)*(b+1)<=d)b++; B[c]=b+1; cnt[c]=cnt[c-1]+B[c]; } long N;cin>>N; if(N==1) { cout<<"0 0\n"; return 0; } N-=1; long R=0; long b=0; while(true) { R++; while(2*(b+1)*(b+1)<=R*R)b++; if(N<=b+1)break; N-=b+1; } vector<pair<long,long> >A; long a=R;b=0; A.push_back(make_pair(a,b)); while(a>0) { a--; if(!f(make_pair(R-1,0),make_pair(a,b)))b++; A.push_back(make_pair(a,b)); } sort(A.begin(),A.end(),f); assert(N<=A.size()); cout<<A[N-1].first<<" "<<A[N-1].second<<endl; }