Submission #305775

---

Source Code Expand

#ifdef KOMAKI_LOCAL
#include <omp.h>
#else
#define NDEBUG
#endif

#include <bits/stdc++.h>
#include <sys/time.h>
#include <unistd.h>
using namespace std;
#define i64         int64_t
#define rep(i, n)   for(i64 i = 0; i < ((i64)(n)); ++i)
#define sz(v)       ((i64)((v).size()))
#define bit(n)      (((i64)1)<<((i64)(n)))
#define all(v)      (v).begin(), (v).end()

template <int POS, class TUPLE> void deploy(std::ostream &os, const TUPLE &tuple){}
template <int POS, class TUPLE, class H, class ...Ts> void deploy(std::ostream &os, const TUPLE &t){ os << (POS == 0 ? "" : ", ") << get<POS>(t); deploy<POS + 1, TUPLE, Ts...>(os, t); }
template <class ...Ts> std::ostream& operator<<(std::ostream &os, const std::tuple<Ts...> &t){ os << "("; deploy<0, std::tuple<Ts...>, Ts...>(os, t); os << ")"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> &v){ int remain = v.size(); os << "{"; for(auto e: v) os << e << (--remain == 0 ? "" : ", "); os << "}"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> &v){ int remain = v.size(); os << "{"; for(auto e: v) os << e << (--remain == 0 ? "" : ", "); os << "}"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::queue<T> &q){ auto qq = q; os << "{"; for(; !qq.empty(); qq.pop()){ os << qq.front() << (qq.size() != 1 ? ", " : ""); } os << "}"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::priority_queue<T> &q){ auto qq = q; os << "{"; for(; !qq.empty(); qq.pop()){ os << qq.top() << (qq.size() != 1 ? ", " : ""); } os << "}"; return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::pair<T, K> &p){ os << "(" << p.first << ", " << p.second << ")"; return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> &mp){ int remain = mp.size(); os << "{"; for(auto e: mp) os << "(" << e.first << " -> " << e.second << ")" << (--remain == 0 ? "" : ", "); os << "}"; return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::unordered_map<T, K> &mp){ int remain = mp.size(); os << "{"; for(auto e: mp) os << "(" << e.first << " -> " << e.second << ")" << (--remain == 0 ? "" : ", "); os << "}"; return os; }
#define DEBUG0() { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << std::endl; }
#define DEBUG1(var0) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << std::endl; }
#define DEBUG2(var0, var1) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << std::endl; }
#define DEBUG3(var0, var1, var2) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << std::endl; }
#define DEBUG4(var0, var1, var2, var3) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << std::endl; }
#define DEBUG5(var0, var1, var2, var3, var4) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << ", " << (#var4) << "=" << (var4) << std::endl; }
#define DEBUG6(var0, var1, var2, var3, var4, var5) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << ", " << (#var4) << "=" << (var4) << ", " << (#var5) << "=" << (var5) << std::endl; }









class Point
{
public:
  i64 x, y;
  Point(int x, int y) : x(x), y(y) {}
  bool operator <(const Point& point) const {
    i64 x_0 = x;
    i64 y_0 = y;
    i64 x_1 = point.x;
    i64 y_1 = point.y;
    i64 xy_0 = abs(x_0) + abs(y_0);
    i64 xy_1 = abs(x_1) + abs(y_1);
    if(xy_0 != xy_1 && abs(x_0) + abs(y_0) < abs(x_1) + abs(y_1)) return true;
    if(xy_0 == xy_1 && x_0 != x_1 && x_0 < x_1) return true;
    if(xy_0 == xy_1 && x_0 == x_1 && y_0 < y_1) return true;
    return false;
  }
};


Point get(i64 n)
{
  if(n == 1) return Point(0, 0);
  n -= 2;
  i64 low = 0;
  i64 high = 2 * 1e9;
  while(low + 1 < high){
    i64 mid = (low + high) / 2;
    i64 total = mid * (mid + 1) / 2 * 4;
    if(total <= n) low = mid;
    else high = mid;
  }
  //DEBUG1(low);
  n -= low * (low + 1) / 2 * 4;
  low += 1;
  //DEBUG1(n);
  if(n == 0) return Point(-low, 0);
  i64 x = -low + 1 + (n - 1) / 2;
  return Point(x, (n % 2 == 0 ? 1 : -1) * (low - abs(x)));
}

int main()
{
  vector<Point> v;
  rep(i, 100)rep(j, 100) v.push_back(Point(i - 5, j - 5));


  sort(all(v));
  //rep(i, sz(v)) cout << v[i].x << ", " << v[i].y << endl;

  i64 k;
  cin >> k;
  rep(i, k){
    i64 n;
    cin >> n;
    Point point = get(n);
    //cout << v[n - 1].x << " " << v[n - 1].y << endl;
    cout << point.x << " " << point.y << endl;
  }
  
}

Submission Info

Judge Result