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
AC × 1
AC × 11
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