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 |
|
|
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 |