Submission #3057857


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

int main() {
  int Q;
  cin >> Q;

  auto f = [](int64 v) {
    auto add = (v + 1) * (v + 2) / 2;
    add *= 4;
    add -= 4 * v;
    add -= 3;
    return add;
  };

  auto g = [](int64 base, int64 v) {
    int64 add = 0;
    if(v < 0) {
      add += 2 * (v + base + 1);
      --add;
    } else {
      add += 2 * base;
      add += 2;
      --add;
      if(v > 0) {
        add += 2 * v;
        if(base == v) --add;
      }
    }
    return add;
  };

  // 2つだけ無効

  // (0,0)
  // (0,1) (1,0)
  // (0,2) (1,1) (2,0)
  // (-0,2)
  // (-0,-2)
  // (0,-2)

  while(Q--) {
    int64 N;
    cin >> N;

    if(N == 1) {
      cout << 0 << " " << 0 << endl;
      continue;
    }

    int64 ok = -1, ng = 1 << 30;
    while(ng - ok > 1) {
      int64 mid = (ok + ng) / 2;
      if(f(mid) < N) ok = mid;
      else ng = mid;
    }
    N -= f(ok);
    ++ok;

    // (0,0) 1つ
    // (1,0),(0,1) 2つ
    // (2,0),(1,1),(0,2) 3つ
    // (3,0),(2,1),(1,2),(0,3) 4つ


    // -2,*   {0}
    // -1,*   {-1, 1}
    // 0,*
    // 1,*
    // 2,*

    int64 ok2 = -ok - 2, ng2 = ok + 1;
    while(ng2 - ok2 > 1) {
      int64 mid = (ok2 + ng2) / 2;
      if(g(ok, mid) < N) ok2 = mid;
      else ng2 = mid;
    }
    if(ok2 != -ok - 2) N -= g(ok, ok2);
    ++ok2;

    vector< pair< int, int > > st;
    int64 sa = abs(ok - abs(ok2));
    st.emplace_back(ok2, -sa);
    st.emplace_back(ok2, sa);
    sort(begin(st), end(st));
    st.erase(unique(begin(st), end(st)), end(st));
    cout << st[N - 1].first << " " << st[N - 1].second << endl;
  }
}

Submission Info

Submission Time
Task B - n-th Points
User ei13333
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1709 Byte
Status AC
Exec Time 297 ms
Memory 2304 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 1 ms 256 KB
subtask1_large_01.txt AC 293 ms 2304 KB
subtask1_mini01.txt AC 247 ms 1024 KB
subtask1_random01.txt AC 255 ms 1408 KB
subtask1_random02.txt AC 256 ms 1408 KB
subtask1_random03.txt AC 254 ms 1408 KB
subtask1_random04.txt AC 296 ms 2176 KB
subtask1_random05.txt AC 296 ms 2176 KB
subtask1_random06.txt AC 296 ms 2176 KB
subtask1_random07.txt AC 297 ms 2176 KB
subtask1_random08.txt AC 290 ms 2176 KB