Submission #305800
Source Code Expand
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const int N=3000; typedef long long ll; const ll inf=1000000000ll; ll sum(ll n) { return (n+1)*n/2; } ll cal(ll n) { ll res=1; if (n==0) return res; ll m1=n/2,m2=n/2; if (n%2==1) m1++; res+=8*sum(m1)-4*m1; res+=8*sum(m2); return res; } ll bs(ll l,ll r, ll n) { ll res=r; while (l<=r) { ll mid=(l+r)/2; //cout<<l<<' '<<r<<' '<<mid<<endl; if (cal(mid)>=n) { res=min(res,mid); r=mid-1; } else l=mid+1; } //cout<<n<<' '<<res<<endl; return res; } void f(ll n) { ll m=bs(0,inf,n); //cout<<m<<endl; ll x,y; if (n==1) { x=0; y=0; } else { n=n-cal(m-1); if (n==1) {x=-m; y=0;} else { x=-m+n/2; if (n%2==0) y=-(m-abs(x)); else y=m-abs(x); } } cout<<x<<' '<<y<<endl; } int main() { //for (int i=0; i<=10; i++) cout<<i<<' '<<cal(i)<<endl; ll o,n; cin>>o; while (o--) { cin>>n; f(n); } return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - n-th Points |
User | asian-2014-1071 |
Language | C++ (G++ 4.6.4) |
Score | 100 |
Code Size | 1290 Byte |
Status | AC |
Exec Time | 651 ms |
Memory | 800 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0_sample_01.txt |
All | subtask0_sample_01.txt, subtask1_large_01.txt, subtask1_mini01.txt, subtask1_random01.txt, subtask1_random02.txt, subtask1_random03.txt, subtask1_random04.txt, subtask1_random05.txt, subtask1_random06.txt, subtask1_random07.txt, subtask1_random08.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0_sample_01.txt | AC | 25 ms | 800 KB |
subtask1_large_01.txt | AC | 609 ms | 672 KB |
subtask1_mini01.txt | AC | 476 ms | 672 KB |
subtask1_random01.txt | AC | 522 ms | 672 KB |
subtask1_random02.txt | AC | 524 ms | 796 KB |
subtask1_random03.txt | AC | 529 ms | 672 KB |
subtask1_random04.txt | AC | 603 ms | 676 KB |
subtask1_random05.txt | AC | 620 ms | 800 KB |
subtask1_random06.txt | AC | 651 ms | 796 KB |
subtask1_random07.txt | AC | 622 ms | 800 KB |
subtask1_random08.txt | AC | 647 ms | 736 KB |