| Task: | Distances |
| Sender: | frederikvase |
| Submission time: | 2026-04-21 13:05:24 +0300 |
| Language: | C++ (C++20) |
| Status: | READY |
| Result: | 100 |
| subtask | verdict | score |
|---|---|---|
| #1 | ACCEPTED | 11 |
| #2 | ACCEPTED | 4 |
| #3 | ACCEPTED | 6 |
| #4 | ACCEPTED | 19 |
| #5 | ACCEPTED | 22 |
| #6 | ACCEPTED | 38 |
| test | verdict | time | subtask | |
|---|---|---|---|---|
| #1 | ACCEPTED | 0.04 s | 1, 4, 6 | details |
| #2 | ACCEPTED | 0.04 s | 1, 2, 3, 4, 5, 6 | details |
| #3 | ACCEPTED | 0.04 s | 1, 3, 4, 5, 6 | details |
| #4 | ACCEPTED | 0.04 s | 1, 2, 4, 6 | details |
| #5 | ACCEPTED | 0.04 s | 1, 3, 4, 5, 6 | details |
| #6 | ACCEPTED | 0.04 s | 1, 4, 6 | details |
| #7 | ACCEPTED | 0.04 s | 1, 4, 6 | details |
| #8 | ACCEPTED | 0.04 s | 1, 2, 4, 6 | details |
| #9 | ACCEPTED | 0.04 s | 1, 3, 4, 5, 6 | details |
| #10 | ACCEPTED | 0.04 s | 1, 4, 5, 6 | details |
| #11 | ACCEPTED | 0.04 s | 1, 4, 6 | details |
| #12 | ACCEPTED | 0.04 s | 1, 4, 6 | details |
| #13 | ACCEPTED | 0.04 s | 1, 4, 6 | details |
| #14 | ACCEPTED | 0.04 s | 1, 6 | details |
| #15 | ACCEPTED | 0.04 s | 1, 2, 6 | details |
| #16 | ACCEPTED | 0.04 s | 4, 6 | details |
| #17 | ACCEPTED | 0.04 s | 4, 6 | details |
| #18 | ACCEPTED | 0.04 s | 3, 4, 5, 6 | details |
| #19 | ACCEPTED | 0.04 s | 4, 5, 6 | details |
| #20 | ACCEPTED | 0.04 s | 4, 5, 6 | details |
| #21 | ACCEPTED | 0.04 s | 5, 6 | details |
| #22 | ACCEPTED | 0.04 s | 5, 6 | details |
| #23 | ACCEPTED | 0.04 s | 2, 6 | details |
| #24 | ACCEPTED | 0.04 s | 3, 4, 5, 6 | details |
| #25 | ACCEPTED | 0.04 s | 4, 5, 6 | details |
| #26 | ACCEPTED | 0.04 s | 4, 5, 6 | details |
| #27 | ACCEPTED | 0.04 s | 5, 6 | details |
| #28 | ACCEPTED | 0.04 s | 5, 6 | details |
| #29 | ACCEPTED | 0.04 s | 2, 6 | details |
| #30 | ACCEPTED | 0.04 s | 3, 4, 5, 6 | details |
| #31 | ACCEPTED | 0.04 s | 4, 5, 6 | details |
| #32 | ACCEPTED | 0.04 s | 4, 5, 6 | details |
| #33 | ACCEPTED | 0.04 s | 4, 5, 6 | details |
| #34 | ACCEPTED | 0.04 s | 5, 6 | details |
| #35 | ACCEPTED | 0.04 s | 5, 6 | details |
| #36 | ACCEPTED | 0.04 s | 5, 6 | details |
| #37 | ACCEPTED | 0.04 s | 6 | details |
| #38 | ACCEPTED | 0.04 s | 6 | details |
| #39 | ACCEPTED | 0.04 s | 2, 6 | details |
| #40 | ACCEPTED | 0.04 s | 6 | details |
| #41 | ACCEPTED | 0.04 s | 6 | details |
| #42 | ACCEPTED | 0.04 s | 6 | details |
| #43 | ACCEPTED | 0.04 s | 6 | details |
| #44 | ACCEPTED | 0.04 s | 6 | details |
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
const int mxn = 1e6;
int sieve[mxn];
void make_sieve() {
for (int i = 2; i < mxn; i++) {
if (sieve[i]) continue;
for (int j = i; j < mxn; j += i) {
sieve[j] = i;
}
}
}
vector<int> divisors(int x) {
vector<int> div = { 1 };
while (x > 1) {
int p = sieve[x];
vector<int> mul = { p };
for (x /= p; sieve[x] == p; x /= p) {
mul.push_back(mul.back() * p);
}
for (int i = sz(div) - 1; i >= 0; i--) {
for (int m : mul) div.push_back(div[i] * m);
}
}
//sort(all(div));
return div;
}
bool is_square(ll x) {
ll xx = sqrt(x) + 0.5;
return xx * xx == x;
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
make_sieve();
auto divs = divisors(1LL*2*2*2*2*3*3*3*5*7);
ll n, k;
cin >> n >> k;
vector<pair<ll, ll>> a;
ll l = 1;
for (ll h : divs) {
for (ll w = h; w <= 1e4; w++) {
if (gcd(h, w) == 1 && is_square(h * h + w * w)) {
l = lcm(l, h);
a.emplace_back(h, w);
}
}
}
for (auto &[h, w] : a) {
w = w * (l / h);
h = l;
}
sort(all(a));
ll mx = 1;
while (mx * (mx + 1) / 2 <= k) mx++;
vector<pair<ll, ll>> res;
res.emplace_back(1, 0);
for (int i = 0; i < mx - 1; i++) {
res.emplace_back(a[i].second + 1, 0);
}
k -= mx * (mx - 1) / 2;
for (int i = 0; i < k; i++) {
res[i].first--;
}
for (int i = 0; sz(res) < n; i++) {
res.emplace_back(-i - (i == 0 ? 0 : ll(7e8)), a[0].first + i + (i == 0 ? 0 : ll(6.5e8)));
}
for (auto [x, y] : res) {
cout << x << " " << y << "\n";
}
return 0;
}
Test details
Test 1
Subtask: 1, 4, 6
Verdict: ACCEPTED
| input |
|---|
| 3 2 |
| correct output |
|---|
| 1 1 1 2 2 2 |
| user output |
|---|
| 0 0 15877 0 0 15120 |
Test 2
Subtask: 1, 2, 3, 4, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 1 0 |
| correct output |
|---|
| 1 0 |
| user output |
|---|
| 1 0 |
Test 3
Subtask: 1, 3, 4, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 2 0 |
| correct output |
|---|
| 1 0 804289383 846930886 |
| user output |
|---|
| 1 0 0 15120 |
Test 4
Subtask: 1, 2, 4, 6
Verdict: ACCEPTED
| input |
|---|
| 2 1 |
| correct output |
|---|
| 1 0 2 0 |
| user output |
|---|
| 1 0 15877 0 |
Test 5
Subtask: 1, 3, 4, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 3 0 |
| correct output |
|---|
| 1 0 804289383 846930886 681692777 714636915 |
| user output |
|---|
| 1 0 0 15120 -700000001 650015121 |
Test 6
Subtask: 1, 4, 6
Verdict: ACCEPTED
| input |
|---|
| 3 1 |
| correct output |
|---|
| 1 0 2 0 804289383 846930886 |
| user output |
|---|
| 1 0 15877 0 0 15120 |
Test 7
Subtask: 1, 4, 6
Verdict: ACCEPTED
| input |
|---|
| 3 2 |
| correct output |
|---|
| 1 1 1 2 2 2 |
| user output |
|---|
| 0 0 15877 0 0 15120 |
Test 8
Subtask: 1, 2, 4, 6
Verdict: ACCEPTED
| input |
|---|
| 3 3 |
| correct output |
|---|
| 1 0 2 0 3 0 |
| user output |
|---|
| 1 0 15877 0 16501 0 |
Test 9
Subtask: 1, 3, 4, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 4 0 |
| correct output |
|---|
| 1 0 804289383 846930886 681692777 714636915 957747793 424238335 |
| user output |
|---|
| 1 0 0 15120 -700000001 650015121 -700000002 650015122 |
Test 10
Subtask: 1, 4, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 4 1 |
| correct output |
|---|
| 1 0 2 0 804289383 846930886 681692777 714636915 |
| user output |
|---|
| 1 0 15877 0 0 15120 -700000001 650015121 |
Test 11
Subtask: 1, 4, 6
Verdict: ACCEPTED
| input |
|---|
| 4 2 |
| correct output |
|---|
| 21392 0 1 0 0 510510 804289383 846930886 |
| user output |
|---|
| 0 0 15877 0 0 15120 -700000001 650015121 |
Test 12
Subtask: 1, 4, 6
Verdict: ACCEPTED
| input |
|---|
| 4 3 |
| correct output |
|---|
| 1 0 2 0 3 0 804289383 846930886 |
| user output |
|---|
| 1 0 15877 0 16501 0 0 15120 |
Test 13
Subtask: 1, 4, 6
Verdict: ACCEPTED
| input |
|---|
| 4 4 |
| correct output |
|---|
| 21392 0 1 0 2 0 0 510510 |
| user output |
|---|
| 0 0 15877 0 16501 0 0 15120 |
Test 14
Subtask: 1, 6
Verdict: ACCEPTED
| input |
|---|
| 4 5 |
| correct output |
|---|
| 21392 0 22600 0 1 0 0 510510 |
| user output |
|---|
| 0 0 15876 0 16501 0 0 15120 |
Test 15
Subtask: 1, 2, 6
Verdict: ACCEPTED
| input |
|---|
| 4 6 |
| correct output |
|---|
| 1 0 2 0 3 0 4 0 |
| user output |
|---|
| 1 0 15877 0 16501 0 16685 0 |
Test 16
Subtask: 4, 6
Verdict: ACCEPTED
| input |
|---|
| 5 5 |
| correct output |
|---|
| 21392 0 22600 0 1 0 0 510510 804289383 846930886 |
| user output |
|---|
| 0 0 15876 0 16501 0 0 15120 -700000001 650015121 |
Test 17
Subtask: 4, 6
Verdict: ACCEPTED
| input |
|---|
| 6 5 |
| correct output |
|---|
| 21392 0 22600 0 1 0 0 510510 804289383 846930886 ... |
| user output |
|---|
| 0 0 15876 0 16501 0 0 15120 -700000001 650015121 ... |
Test 18
Subtask: 3, 4, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 98 0 |
| correct output |
|---|
| 1 0 804289383 846930886 681692777 714636915 957747793 424238335 719885386 649760492 ... |
| user output |
|---|
| 1 0 0 15120 -700000001 650015121 -700000002 650015122 -700000003 650015123 ... |
Test 19
Subtask: 4, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 98 97 |
| correct output |
|---|
| 21392 0 22600 0 30056 0 34848 0 38584 0 ... |
| user output |
|---|
| 0 0 15876 0 16500 0 16684 0 16965 0 ... |
Test 20
Subtask: 4, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 98 98 |
| correct output |
|---|
| 21392 0 22600 0 30056 0 34848 0 38584 0 ... |
| user output |
|---|
| 0 0 15876 0 16500 0 16684 0 16965 0 ... |
Test 21
Subtask: 5, 6
Verdict: ACCEPTED
| input |
|---|
| 98 1185 |
| correct output |
|---|
| 21392 0 22600 0 30056 0 34848 0 38584 0 ... |
| user output |
|---|
| 0 0 15876 0 16500 0 16684 0 16965 0 ... |
Test 22
Subtask: 5, 6
Verdict: ACCEPTED
| input |
|---|
| 98 1188 |
| correct output |
|---|
| 21392 0 22600 0 30056 0 34848 0 38584 0 ... |
| user output |
|---|
| 0 0 15876 0 16500 0 16684 0 16965 0 ... |
Test 23
Subtask: 2, 6
Verdict: ACCEPTED
| input |
|---|
| 98 4753 |
| correct output |
|---|
| 1 0 2 0 3 0 4 0 5 0 ... |
| user output |
|---|
| 1 0 15877 0 16501 0 16685 0 16966 0 ... |
Test 24
Subtask: 3, 4, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 99 0 |
| correct output |
|---|
| 1 0 804289383 846930886 681692777 714636915 957747793 424238335 719885386 649760492 ... |
| user output |
|---|
| 1 0 0 15120 -700000001 650015121 -700000002 650015122 -700000003 650015123 ... |
Test 25
Subtask: 4, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 99 98 |
| correct output |
|---|
| 21392 0 22600 0 30056 0 34848 0 38584 0 ... |
| user output |
|---|
| 0 0 15876 0 16500 0 16684 0 16965 0 ... |
Test 26
Subtask: 4, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 99 99 |
| correct output |
|---|
| 21392 0 22600 0 30056 0 34848 0 38584 0 ... |
| user output |
|---|
| 0 0 15876 0 16500 0 16684 0 16965 0 ... |
Test 27
Subtask: 5, 6
Verdict: ACCEPTED
| input |
|---|
| 99 1201 |
| correct output |
|---|
| 21392 0 22600 0 30056 0 34848 0 38584 0 ... |
| user output |
|---|
| 0 0 15876 0 16500 0 16684 0 16965 0 ... |
Test 28
Subtask: 5, 6
Verdict: ACCEPTED
| input |
|---|
| 99 1212 |
| correct output |
|---|
| 21392 0 22600 0 30056 0 34848 0 38584 0 ... |
| user output |
|---|
| 0 0 15876 0 16500 0 16684 0 16965 0 ... |
Test 29
Subtask: 2, 6
Verdict: ACCEPTED
| input |
|---|
| 99 4851 |
| correct output |
|---|
| 1 0 2 0 3 0 4 0 5 0 ... |
| user output |
|---|
| 1 0 15877 0 16501 0 16685 0 16966 0 ... |
Test 30
Subtask: 3, 4, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 100 0 |
| correct output |
|---|
| 1 0 804289383 846930886 681692777 714636915 957747793 424238335 719885386 649760492 ... |
| user output |
|---|
| 1 0 0 15120 -700000001 650015121 -700000002 650015122 -700000003 650015123 ... |
Test 31
Subtask: 4, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 100 1 |
| correct output |
|---|
| 1 0 2 0 804289383 846930886 681692777 714636915 957747793 424238335 ... |
| user output |
|---|
| 1 0 15877 0 0 15120 -700000001 650015121 -700000002 650015122 ... |
Test 32
Subtask: 4, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 100 5 |
| correct output |
|---|
| 21392 0 22600 0 1 0 0 510510 804289383 846930886 ... |
| user output |
|---|
| 0 0 15876 0 16501 0 0 15120 -700000001 650015121 ... |
Test 33
Subtask: 4, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 100 100 |
| correct output |
|---|
| 21392 0 22600 0 30056 0 34848 0 38584 0 ... |
| user output |
|---|
| 0 0 15876 0 16500 0 16684 0 16965 0 ... |
Test 34
Subtask: 5, 6
Verdict: ACCEPTED
| input |
|---|
| 100 1000 |
| correct output |
|---|
| 21392 0 22600 0 30056 0 34848 0 38584 0 ... |
| user output |
|---|
| 0 0 15876 0 16500 0 16684 0 16965 0 ... |
Test 35
Subtask: 5, 6
Verdict: ACCEPTED
| input |
|---|
| 100 1232 |
| correct output |
|---|
| 21392 0 22600 0 30056 0 34848 0 38584 0 ... |
| user output |
|---|
| 0 0 15876 0 16500 0 16684 0 16965 0 ... |
Test 36
Subtask: 5, 6
Verdict: ACCEPTED
| input |
|---|
| 100 1237 |
| correct output |
|---|
| 21392 0 22600 0 30056 0 34848 0 38584 0 ... |
| user output |
|---|
| 0 0 15876 0 16500 0 16684 0 16965 0 ... |
Test 37
Subtask: 6
Verdict: ACCEPTED
| input |
|---|
| 100 2222 |
| correct output |
|---|
| 21392 0 22600 0 30056 0 34848 0 38584 0 ... |
| user output |
|---|
| 0 0 15876 0 16500 0 16684 0 16965 0 ... |
Test 38
Subtask: 6
Verdict: ACCEPTED
| input |
|---|
| 100 3395 |
| correct output |
|---|
| 21392 0 22600 0 30056 0 34848 0 38584 0 ... |
| user output |
|---|
| 0 0 15876 0 16500 0 16684 0 16965 0 ... |
Test 39
Subtask: 2, 6
Verdict: ACCEPTED
| input |
|---|
| 100 4950 |
| correct output |
|---|
| 1 0 2 0 3 0 4 0 5 0 ... |
| user output |
|---|
| 1 0 15877 0 16501 0 16685 0 16966 0 ... |
Test 40
Subtask: 6
Verdict: ACCEPTED
| input |
|---|
| 100 4949 |
| correct output |
|---|
| 21392 0 22600 0 30056 0 34848 0 38584 0 ... |
| user output |
|---|
| 0 0 15876 0 16500 0 16684 0 16965 0 ... |
Test 41
Subtask: 6
Verdict: ACCEPTED
| input |
|---|
| 100 4948 |
| correct output |
|---|
| 21392 0 22600 0 30056 0 34848 0 38584 0 ... |
| user output |
|---|
| 0 0 15876 0 16500 0 16684 0 16965 0 ... |
Test 42
Subtask: 6
Verdict: ACCEPTED
| input |
|---|
| 100 4930 |
| correct output |
|---|
| 21392 0 22600 0 30056 0 34848 0 38584 0 ... |
| user output |
|---|
| 0 0 15876 0 16500 0 16684 0 16965 0 ... |
Test 43
Subtask: 6
Verdict: ACCEPTED
| input |
|---|
| 100 4920 |
| correct output |
|---|
| 21392 0 22600 0 30056 0 34848 0 38584 0 ... |
| user output |
|---|
| 0 0 15876 0 16500 0 16684 0 16965 0 ... |
Test 44
Subtask: 6
Verdict: ACCEPTED
| input |
|---|
| 100 4900 |
| correct output |
|---|
| 21392 0 22600 0 30056 0 34848 0 38584 0 ... |
| user output |
|---|
| 0 0 15876 0 16500 0 16684 0 16965 0 ... |