QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#245273 | #7661. Japanese Lottery | Yarema# | AC ✓ | 1093ms | 11664kb | C++17 | 4.0kb | 2023-11-09 20:17:25 | 2023-11-09 20:17:25 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
mt19937 rng;
struct Node
{
int l, r;
int x;
int y;
int val;
void init(int h, int rod)
{
l = r = -1;
x = h;
y = rng();
val = rod;
}
};
const int N = 400'447;
struct Treap
{
Node A[N];
int sz = 0;
int newNode(int h, int r)
{
A[sz].init(h, r);
return sz++;
}
PII split(int v, int h)
{
if (v == -1)
return {-1, -1};
PII res;
if (h < A[v].x)
{
res = split(A[v].l, h);
A[v].l = res.second;
res.second = v;
}
else
{
// split(v, val)
res = split(A[v].r, h);
A[v].r = res.first;
res.first = v;
}
return res;
}
int merge(int v, int u)
{
if (v == -1) return u;
if (u == -1) return v;
int res;
if (A[v].y > A[u].y)
{
res = merge(A[v].r, u);
A[v].r = res;
res = v;
}
else
{
res = merge(v, A[u].l);
A[u].l = res;
res = u;
}
return res;
}
int getVal(int v, int h)
{
if (v == -1)
return -1;
if (A[v].x == h)
return A[v].val;
if (A[v].x > h)
return getVal(A[v].l, h);
else
return getVal(A[v].r, h);
}
int lower_bound(int v, int h)
{
if (v == -1)
return -1;
if (A[v].x > h)
return lower_bound(A[v].l, h);
else
{
int x = lower_bound(A[v].r, h);
if (x == -1)
x = A[v].val;
return x;
}
}
int insert(int v, int h, int r)
{
if (getVal(v, h) == -1)
{
PII p = split(v, h);
v = merge(p.F, newNode(h, r));
v = merge(v, p.S);
return v;
}
else
{
PII p = split(v, h - 1);
PII p2 = split(p.S, h);
return merge(p.F, p2.S);
}
}
void print(int v)
{
if (v == -1)
return;
print(A[v].l);
cerr << A[v].x << ' ' << A[v].val << '\n';
print(A[v].r);
}
} T;
int f(const VI& p)
{
int cnt = 0;
int n = SZ(p);
VI used(n, 0);
FOR (i, 0, n)
{
if (!used[i])
{
int x = p[i];
used[i] = 1;
while (p[x] != p[i])
{
used[x] = 1;
cnt++;
x = p[x];
}
}
}
return cnt;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(15);
int n, h, q;
cin >> n >> h >> q;
vector<int> s(n, -1);
FOR (i, 0, n)
{
s[i] = T.insert(s[i], 0, i);
s[i] = T.insert(s[i], h + 47, i);
}
VI p(n);
VI p0(n);
iota(ALL(p), 0);
iota(ALL(p0), 0);
FOR (i, 0, q)
{
int y, x1, x2;
cin >> y >> x1 >> x2;
x1--, x2--;
int idx1 = -1, idx2 = -1;
FOR (j, 0, n)
{
int val = T.lower_bound(s[j], y);
if (val == x1)
idx1 = j;
if (val == x2)
idx2 = j;
}
//cerr << i << ": " << idx1 << ' ' << idx2 << '\n';
//FOR (k, 0, n)
// cerr << p[k] << ' ';
//cerr << "\n";
assert(idx1 != -1);
assert(idx2 != -1);
assert(idx1 != idx2);
swap(p[p0[idx1]], p[p0[idx2]]);
swap(p0[idx1], p0[idx2]);
//FOR (k, 0, n)
// cerr << p[k] << ' ';
//cerr << "\n";
//
//cerr << idx1 << ' ' << idx2 << '\n';
//cerr << '\n';
s[idx1] = T.insert(s[idx1], y, x2);
s[idx2] = T.insert(s[idx2], y, x1);
PII p1 = T.split(s[idx1], y);
PII p2 = T.split(s[idx2], y);
//cerr << "SPLIT\n";
//T.print(p1.F);
//cerr << '\n';
//T.print(p1.S);
//cerr << '\n';
//T.print(p2.F);
//cerr << '\n';
//T.print(p2.S);
//cerr << '\n';
s[idx1] = T.merge(p1.F, p2.S);
s[idx2] = T.merge(p2.F, p1.S);
//cerr << s[idx1] << ' ' << p0[idx1] << '\n';
//cerr << s[idx2] << ' ' << p0[idx2] << '\n';
//
//cerr << "DUPA\n";
//FOR (j, 0, n)
//{
// cerr << j << ' ' << s[j] << ":\n";
// T.print(s[j]);
//}
//cerr << "\n\n";
cout << f(p) << '\n';
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3784kb
input:
4 6 7 1 1 2 2 3 4 4 3 4 5 1 2 6 3 4 3 2 3 6 3 4
output:
1 2 1 0 1 2 1
result:
ok 7 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
5 9 12 1 3 4 2 1 2 3 2 3 4 4 5 5 2 1 6 4 3 7 2 3 8 4 3 9 4 5 6 4 3 7 2 3 1 3 4
output:
1 2 3 4 3 2 3 4 3 4 3 2
result:
ok 12 lines
Test #3:
score: 0
Accepted
time: 158ms
memory: 7876kb
input:
20 60 200000 49 11 10 18 6 7 24 4 5 56 10 9 14 19 18 44 2 3 4 3 4 24 4 5 30 4 5 56 10 9 44 2 3 50 10 9 43 6 7 50 9 10 18 7 6 13 16 17 57 16 15 52 7 6 55 7 8 10 18 19 47 17 16 11 11 12 33 17 18 7 11 10 57 15 16 45 9 8 47 17 16 56 17 16 10 18 19 19 5 4 21 9 8 53 10 11 22 8 9 4 4 3 13 16 17 7 11 10 4 8...
output:
1 2 3 4 5 6 7 6 7 6 5 6 5 4 5 6 7 6 7 6 5 6 7 6 5 6 7 6 7 6 5 6 7 6 7 6 5 4 3 4 3 4 5 4 5 6 7 8 9 10 9 10 9 8 9 8 9 8 7 8 9 8 9 8 9 10 9 10 9 10 9 10 11 10 11 10 11 10 9 8 7 8 9 10 11 12 13 14 13 12 13 12 13 12 11 12 13 12 11 10 11 10 11 10 11 12 11 10 11 10 9 10 11 12 11 10 9 8 7 6 7 8 9 10 9 10 11...
result:
ok 200000 lines
Test #4:
score: 0
Accepted
time: 279ms
memory: 9080kb
input:
20 400 200000 84 15 16 93 20 19 8 4 5 334 11 10 265 14 13 30 16 15 23 18 19 122 1 2 367 10 9 17 17 16 240 4 5 86 6 7 368 6 5 33 17 16 271 19 20 243 18 19 71 9 8 182 16 15 42 1 2 300 14 13 259 17 16 35 6 7 269 8 7 279 8 9 360 20 19 84 15 16 84 8 7 204 9 10 50 4 5 23 18 19 335 7 8 391 8 7 353 2 3 304 ...
output:
1 2 3 4 5 4 5 6 7 8 7 8 9 10 9 10 11 10 9 8 9 8 9 8 7 6 7 8 9 10 9 10 11 10 9 8 9 10 11 10 9 8 9 8 9 10 9 10 9 10 11 10 11 12 11 10 9 10 9 10 11 12 13 12 13 14 13 14 15 14 13 12 11 10 11 10 9 10 11 10 9 10 9 10 9 10 11 12 13 14 15 14 13 12 13 14 15 14 13 14 15 14 13 14 13 12 13 14 13 12 11 12 11 12 ...
result:
ok 200000 lines
Test #5:
score: 0
Accepted
time: 882ms
memory: 10120kb
input:
20 100000 200000 84187 5 4 81775 15 16 35852 2 3 43675 14 15 37167 10 11 28631 9 10 44662 10 9 68558 11 10 63694 11 10 51521 14 15 7418 20 19 7871 16 15 73663 9 8 54430 12 11 86737 11 10 234 5 6 3675 5 4 81807 6 5 46365 18 17 85278 4 3 83185 18 17 37617 4 3 22217 10 9 55279 11 10 4864 3 4 14664 4 5 ...
output:
1 2 3 4 5 6 5 6 5 4 5 4 5 6 7 8 7 8 9 10 9 8 7 8 9 8 9 10 9 8 7 8 9 8 9 8 9 8 9 8 9 10 9 8 7 8 9 10 11 12 11 10 9 10 11 10 11 10 11 10 9 8 9 10 11 12 13 14 15 14 13 12 13 14 13 14 15 16 15 14 15 14 15 16 15 14 13 12 13 12 11 12 13 14 13 14 13 14 15 14 13 12 11 12 11 10 11 12 11 12 13 14 15 14 15 14 ...
result:
ok 200000 lines
Test #6:
score: 0
Accepted
time: 938ms
memory: 8468kb
input:
20 100000 200000 40254 13 12 43097 3 2 51140 2 3 361 10 11 38355 10 9 24292 5 4 78434 17 18 83046 5 6 30372 16 17 29752 16 15 465 14 15 51028 6 5 56823 4 3 16137 2 1 6086 6 5 68895 4 3 99901 6 7 59411 15 14 80531 12 11 48387 12 11 18031 8 7 62565 7 8 43946 1 2 22091 8 7 94502 12 11 92202 10 9 19028 ...
output:
1 2 1 2 3 4 5 6 7 8 9 8 9 10 11 10 11 10 11 10 11 10 11 12 13 12 13 12 13 12 11 10 9 10 9 8 9 8 7 8 9 10 9 10 11 12 13 14 15 14 13 14 15 14 15 16 15 14 15 14 15 16 15 16 17 16 15 16 15 14 15 14 15 14 15 16 15 14 15 16 17 16 15 14 13 12 13 14 15 16 15 14 13 14 13 12 13 14 13 12 13 12 13 14 13 12 13 1...
result:
ok 200000 lines
Test #7:
score: 0
Accepted
time: 842ms
memory: 7828kb
input:
20 100000 200000 96456 3 4 14229 6 5 28460 7 6 63794 8 7 38040 18 17 76605 10 9 60637 10 9 28600 6 5 16761 2 1 57006 18 17 7974 2 1 25118 8 7 33654 5 6 73468 7 6 37986 2 3 71752 10 11 2025 20 19 34790 9 10 28222 11 10 76172 18 17 78374 11 12 19618 5 6 27451 9 10 97316 17 16 88086 5 4 52185 3 2 1848 ...
output:
1 2 3 4 5 6 5 4 5 4 3 2 3 4 5 6 7 8 7 8 9 8 7 8 9 8 7 8 9 8 7 8 9 10 9 10 11 10 9 8 7 8 9 10 9 10 11 10 11 12 11 12 13 14 13 14 13 14 13 12 11 12 11 10 9 10 9 8 9 10 11 12 11 12 13 12 11 12 13 14 13 14 15 14 13 12 13 14 13 14 13 12 11 12 13 14 13 14 15 16 15 14 13 12 13 12 11 12 13 14 15 16 15 16 15...
result:
ok 200000 lines
Test #8:
score: 0
Accepted
time: 1093ms
memory: 11384kb
input:
20 200000 200000 172830 14 15 145499 4 5 121702 11 12 163484 4 5 152838 19 18 107244 3 2 84072 19 20 184634 13 14 116717 3 2 85597 2 1 33220 15 16 42087 18 19 146098 20 19 158127 17 18 5564 11 10 139454 13 14 104883 5 4 15585 20 19 12017 4 3 191118 16 17 50882 11 10 193754 3 2 94893 8 7 198039 10 11...
output:
1 2 3 2 3 4 5 6 5 6 7 6 5 6 7 6 7 8 9 10 9 10 11 12 11 12 13 12 13 12 11 12 13 14 13 12 11 10 9 10 11 10 9 8 7 6 7 6 5 6 7 8 9 8 9 10 11 10 11 10 11 10 11 10 11 12 11 10 9 10 11 10 11 12 11 12 13 12 11 10 9 8 9 10 9 8 9 8 9 10 11 12 11 12 13 12 13 14 13 14 13 14 13 12 13 12 11 12 13 14 13 14 13 14 1...
result:
ok 200000 lines
Test #9:
score: 0
Accepted
time: 731ms
memory: 10800kb
input:
20 200000 200000 37255 12 13 173520 20 19 171711 10 11 170534 4 5 188420 4 5 178109 13 12 161738 8 7 46406 16 15 15403 12 13 36236 15 16 184131 14 15 2224 20 19 14232 8 9 193647 9 10 32178 7 8 156588 13 12 27693 15 14 199725 13 14 20541 11 12 42484 2 3 158565 6 5 35098 6 5 19280 8 7 32963 16 15 1832...
output:
1 2 3 4 3 2 3 4 5 4 5 4 5 6 5 4 3 4 5 6 7 6 7 8 9 8 7 6 7 8 7 8 9 10 9 10 11 10 11 12 11 10 9 8 9 10 9 10 11 10 11 12 11 10 11 10 11 10 9 10 11 10 11 10 9 10 9 8 9 8 9 8 9 8 7 8 9 8 9 10 11 12 13 12 11 12 11 12 13 14 13 12 11 12 13 12 11 12 11 10 11 12 11 10 11 12 13 14 15 14 15 16 15 16 15 14 13 14...
result:
ok 200000 lines
Test #10:
score: 0
Accepted
time: 834ms
memory: 9732kb
input:
20 200000 200000 197148 3 2 582 16 17 41009 18 17 32765 10 9 184076 10 11 31781 15 16 190437 13 14 156461 5 6 41861 19 20 191238 12 13 30823 5 6 191965 11 10 2156 6 7 153376 11 10 196640 6 7 26980 14 15 11584 16 17 4235 4 5 191086 9 10 176925 15 16 178923 6 5 182757 5 4 44084 5 6 20361 8 9 47394 10 ...
output:
1 2 3 4 5 6 7 8 9 10 9 8 9 10 9 10 9 10 9 8 9 8 7 8 9 8 9 10 11 12 11 12 11 10 11 10 11 12 13 14 13 14 13 14 15 14 15 14 15 14 13 14 15 14 15 16 15 14 13 12 13 12 13 14 13 12 11 12 13 12 11 12 13 12 13 14 13 14 15 14 15 14 13 12 13 12 11 10 9 10 11 12 11 10 11 10 9 10 9 10 11 12 11 10 9 8 9 10 11 12...
result:
ok 200000 lines
Test #11:
score: 0
Accepted
time: 933ms
memory: 11236kb
input:
20 200000 200000 180789 4 5 35390 7 8 41300 3 4 176065 5 6 166749 5 6 2315 9 10 181603 20 19 167830 12 13 184750 3 4 8082 8 9 196150 5 4 153925 2 3 44039 15 16 160016 16 17 186290 9 10 181864 17 16 194136 18 17 163921 9 8 36191 3 4 158737 15 14 5928 11 12 46919 12 11 26484 13 12 31363 18 19 20924 4 ...
output:
1 2 3 4 3 4 5 6 5 6 7 8 9 10 9 8 9 8 7 8 9 8 9 10 11 10 11 10 11 12 11 12 13 12 13 12 11 12 11 12 13 12 11 12 13 14 13 12 11 12 11 12 11 10 11 10 11 10 9 10 11 12 13 14 13 12 11 12 11 10 9 10 11 12 13 12 13 12 11 12 13 14 15 16 15 14 13 14 15 14 15 14 15 14 15 14 15 14 13 12 11 12 11 12 13 12 13 12 ...
result:
ok 200000 lines
Test #12:
score: 0
Accepted
time: 14ms
memory: 5948kb
input:
6 20 32767 1 1 2 2 2 3 1 1 2 3 3 4 1 1 2 2 2 3 1 1 2 4 4 5 1 1 2 2 2 3 1 1 2 3 3 4 1 1 2 2 2 3 1 1 2 5 5 6 1 1 2 2 2 3 1 1 2 3 3 4 1 1 2 2 2 3 1 1 2 4 4 5 1 1 2 2 2 3 1 1 2 3 3 4 1 1 2 2 2 3 1 1 2 6 1 2 1 1 2 2 2 3 1 1 2 3 3 4 1 1 2 2 2 3 1 1 2 4 4 5 1 1 2 2 2 3 1 1 2 3 3 4 1 1 2 2 2 3 1 1 2 5 5 6 1...
output:
1 2 1 2 3 2 1 2 3 4 3 2 3 2 1 2 3 4 3 4 5 4 3 2 3 4 3 2 3 2 1 2 1 2 3 4 3 2 3 4 3 4 5 4 3 2 3 2 1 2 3 4 3 2 3 2 1 2 3 2 1 0 1 2 1 2 1 2 3 2 3 4 3 4 3 2 3 2 3 4 3 4 3 4 5 4 5 4 3 4 3 2 3 2 3 2 3 2 1 2 3 4 3 4 5 4 3 2 3 4 3 2 3 2 1 2 3 4 3 2 3 2 1 0 1 2 1 2 3 2 1 2 3 2 1 2 3 4 3 2 3 4 3 4 5 4 3 4 5 4 ...
result:
ok 32767 lines
Test #13:
score: 0
Accepted
time: 14ms
memory: 4216kb
input:
7 25 28333 6 6 7 11 5 6 6 6 7 11 5 6 6 6 7 5 5 6 11 5 6 5 5 6 5 5 6 15 4 5 11 5 6 6 6 7 5 5 6 6 6 7 15 4 5 11 5 6 10 4 5 6 6 7 11 5 6 10 4 5 6 6 7 5 5 6 4 4 5 11 5 6 10 4 5 5 5 6 4 4 5 10 4 5 5 5 6 4 4 5 15 4 5 6 6 7 5 5 6 4 4 5 11 5 6 6 6 7 5 5 6 11 5 6 10 4 5 6 6 7 5 5 6 11 5 6 10 4 5 6 6 7 5 5 6 ...
output:
1 2 1 0 1 2 1 2 1 2 3 2 1 2 1 2 3 2 1 0 1 2 3 2 3 2 3 2 1 2 1 0 1 2 1 2 3 2 3 2 1 0 1 2 3 2 3 2 3 2 3 2 1 2 3 2 3 2 3 2 1 2 3 2 3 4 3 4 3 2 1 2 3 2 1 2 3 2 3 2 1 2 3 4 3 2 3 2 1 2 3 4 3 2 1 0 1 2 3 4 3 4 3 4 3 4 3 2 1 2 3 2 3 2 3 2 3 2 3 4 3 2 3 4 3 2 1 2 1 2 3 2 3 4 3 4 3 2 3 2 3 4 3 4 3 4 3 4 3 2 ...
result:
ok 28333 lines
Test #14:
score: 0
Accepted
time: 172ms
memory: 9256kb
input:
20 200 199960 189 2 3 187 3 4 186 2 3 180 5 6 179 4 5 178 3 4 175 6 7 174 5 6 173 4 5 172 3 4 171 2 3 170 1 2 169 7 8 168 6 7 167 5 6 166 4 5 165 3 4 164 2 3 162 8 9 161 7 8 160 6 7 159 5 6 158 4 5 154 9 10 153 8 9 152 7 8 151 6 7 150 5 6 149 4 5 148 3 4 145 10 11 144 9 10 143 8 9 142 7 8 141 6 7 14...
output:
1 2 1 2 3 4 5 4 5 4 5 6 7 6 5 6 5 6 7 6 5 4 5 6 7 8 9 8 9 8 9 8 9 10 9 8 9 10 9 8 9 10 11 10 11 12 11 12 11 10 11 12 13 12 11 10 11 10 11 10 11 12 11 12 13 14 13 12 13 12 13 12 13 12 13 14 13 14 15 16 15 14 15 14 15 14 13 14 15 16 17 16 15 16 17 18 17 18 17 18 17 18 17 18 17 18 17 18 19 18 19 18 19 ...
result:
ok 199960 lines
Test #15:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
3 2 2 1 2 1 2 2 3
output:
1 2
result:
ok 2 lines
Test #16:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
20 40 38 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 10 10 10 11 11 11 12 12 12 13 13 13 14 14 14 15 15 15 16 16 16 17 17 17 18 18 18 19 19 19 20 21 1 2 22 2 3 23 3 4 24 4 5 25 5 6 26 6 7 27 7 8 28 8 9 29 9 10 30 10 11 31 11 12 32 12 13 33 13 14 34 14 15 35 15 16 36 16 17 37 17 18 38 18 19 3...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 18 19 18 19 18 19 18 19 18 19 18 19 18 19 18 19 18 19 18
result:
ok 38 lines
Test #17:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
5 10 10 1 1 2 2 2 3 3 3 4 4 4 5 5 1 2 6 2 3 7 3 4 8 1 2 9 2 3 10 1 2
output:
1 2 3 4 3 4 3 4 3 2
result:
ok 10 lines
Test #18:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
5 10 10 6 2 3 2 2 3 8 1 2 9 2 3 1 1 2 3 3 4 4 4 5 10 1 2 7 3 4 5 1 2
output:
1 0 1 2 1 2 3 4 3 2
result:
ok 10 lines
Test #19:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
5 10 20 1 1 2 2 2 3 3 3 4 4 4 5 5 1 2 6 2 3 7 3 4 8 1 2 9 2 3 10 1 2 6 2 3 2 2 3 8 1 2 9 2 3 1 1 2 3 3 4 4 4 5 10 1 2 7 3 4 5 1 2
output:
1 2 3 4 3 4 3 4 3 2 1 2 3 2 1 2 1 2 1 0
result:
ok 20 lines
Test #20:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
5 10 20 6 2 3 2 2 3 8 1 2 9 2 3 1 1 2 3 3 4 4 4 5 10 1 2 7 3 4 5 1 2 1 1 2 2 2 3 3 3 4 4 4 5 5 1 2 6 2 3 7 3 4 8 1 2 9 2 3 10 1 2
output:
1 0 1 2 1 2 3 4 3 2 3 4 3 2 3 2 1 2 1 0
result:
ok 20 lines
Test #21:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
5 30 30 1 1 2 2 2 3 3 3 4 4 4 5 5 1 2 6 2 3 7 3 4 8 1 2 9 2 3 10 1 2 11 4 5 12 3 4 11 4 5 13 4 5 12 3 4 15 2 3 14 1 2 16 3 4 17 2 3 15 2 3 21 1 2 22 2 3 23 3 4 24 4 5 25 1 2 26 2 3 27 3 4 28 1 2 29 2 3 30 1 2
output:
1 2 3 4 3 4 3 4 3 2 3 4 3 4 3 4 3 4 3 4 3 2 1 2 3 4 3 4 3 4
result:
ok 30 lines
Test #22:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
20 40 38 17 17 18 8 8 9 14 14 15 19 19 20 21 1 2 22 2 3 34 14 15 6 6 7 16 16 17 38 18 19 23 3 4 33 13 14 7 7 8 31 11 12 9 9 10 10 10 11 11 11 12 1 1 2 35 15 16 32 12 13 2 2 3 28 8 9 29 9 10 30 10 11 18 18 19 3 3 4 39 19 20 15 15 16 36 16 17 4 4 5 5 5 6 12 12 13 13 13 14 26 6 7 27 7 8 37 17 18 24 4 5...
output:
1 2 3 4 5 6 5 6 7 8 9 10 11 12 13 14 13 12 13 14 15 14 15 16 15 14 15 16 15 16 17 16 17 16 17 18 19 18
result:
ok 38 lines
Test #23:
score: 0
Accepted
time: 851ms
memory: 11336kb
input:
20 200000 200000 1 17 16 201 16 17 401 10 9 601 14 15 801 9 8 1001 19 20 1201 3 2 1401 2 3 1601 10 9 1801 6 7 2001 19 20 2201 6 7 2401 4 5 2601 2 1 2801 16 17 3001 10 9 3201 8 7 3401 18 19 3601 2 3 3801 4 5 4001 5 6 4201 19 18 4401 11 12 4601 9 8 4801 14 13 5001 3 2 5201 18 19 5401 15 16 5601 14 15 ...
output:
1 0 1 2 3 4 5 4 3 4 3 2 3 4 5 6 7 8 9 8 9 8 9 8 9 8 9 10 9 8 9 10 9 10 9 10 11 10 11 10 9 10 11 12 13 12 13 12 13 14 15 14 13 12 13 12 13 12 11 12 13 14 15 14 13 14 13 14 15 16 15 14 13 12 13 12 13 14 13 14 13 12 11 10 11 10 11 12 11 12 11 12 11 12 11 12 11 12 13 12 13 14 13 14 13 12 13 12 13 14 13 ...
result:
ok 200000 lines
Test #24:
score: 0
Accepted
time: 959ms
memory: 11380kb
input:
20 200000 200000 1 13 14 401 9 10 801 19 18 1201 3 4 1601 18 19 2001 15 14 2401 10 9 2801 2 1 3201 8 9 3601 13 12 4001 14 13 4401 3 4 4801 19 20 5201 15 14 5601 12 13 6001 2 3 6401 17 16 6801 1 2 7201 8 7 7601 14 13 8001 14 15 8401 7 8 8801 18 19 9201 5 4 9601 13 12 10001 20 19 10401 9 8 10801 5 4 1...
output:
1 2 3 4 3 4 3 4 5 6 5 4 5 6 5 6 7 6 7 6 7 6 7 8 9 8 7 6 7 8 9 8 9 8 9 8 7 8 9 8 9 8 9 8 7 8 7 8 9 8 9 10 11 12 11 12 13 12 13 12 11 10 11 10 9 10 11 10 11 12 11 12 11 10 11 12 13 12 13 12 11 10 11 12 13 14 13 12 13 12 11 10 11 10 11 12 13 12 13 12 13 12 13 12 13 14 15 14 13 14 15 14 13 14 13 14 13 1...
result:
ok 200000 lines
Test #25:
score: 0
Accepted
time: 961ms
memory: 11632kb
input:
20 200000 200000 1 8 7 601 16 15 1201 3 2 1801 1 2 2401 4 5 3001 7 8 3601 11 10 4201 4 5 4801 17 18 5401 6 5 6001 13 14 6601 16 15 7201 9 8 7801 13 12 8401 16 17 9001 2 3 9601 12 11 10201 10 9 10801 2 3 11401 3 4 12001 13 14 12601 14 13 13201 10 9 13801 9 10 14401 12 13 15001 7 6 15601 16 17 16201 1...
output:
1 2 3 4 5 4 5 4 5 6 7 6 7 8 9 8 9 10 11 12 11 12 11 12 11 12 11 10 9 8 9 10 9 10 9 8 7 8 9 10 11 12 11 10 11 12 11 12 13 12 11 10 11 10 11 10 11 10 11 12 13 14 13 12 11 12 13 14 13 12 11 12 13 12 11 10 11 10 11 12 11 10 11 10 11 10 11 10 11 10 9 10 11 12 13 14 15 14 13 12 13 12 13 14 15 16 15 16 15 ...
result:
ok 200000 lines
Test #26:
score: 0
Accepted
time: 995ms
memory: 11384kb
input:
20 200000 200000 1 15 16 801 7 8 1601 19 18 2401 5 4 3201 7 6 4001 1 2 4801 13 12 5601 16 17 6401 10 11 7201 16 15 8001 9 10 8801 18 17 9601 17 18 10401 3 4 11201 2 3 12001 16 15 12801 19 20 13601 18 17 14401 5 4 15201 9 10 16001 8 7 16801 19 18 17601 19 20 18401 13 14 19201 16 15 20001 17 16 20801 ...
output:
1 2 3 4 5 6 7 8 9 8 9 10 9 10 11 12 13 14 13 12 11 10 11 12 11 12 11 12 13 12 11 12 11 12 13 14 13 14 13 14 15 14 15 14 13 14 15 14 13 14 15 14 13 14 15 16 15 16 15 16 15 16 15 16 17 18 17 16 17 16 15 16 17 18 17 18 17 16 17 18 17 16 15 14 15 14 15 14 13 12 13 12 13 14 13 14 15 14 13 14 15 14 13 14 ...
result:
ok 200000 lines
Test #27:
score: 0
Accepted
time: 1043ms
memory: 11664kb
input:
20 200000 200000 1 10 9 1001 14 13 2001 17 18 3001 13 12 4001 13 14 5001 2 1 6001 11 12 7001 8 7 8001 3 2 9001 2 1 10001 3 4 11001 3 2 12001 4 5 13001 18 17 14001 8 7 15001 7 6 16001 11 10 17001 15 16 18001 14 15 19001 2 3 20001 4 3 21001 15 16 22001 15 16 23001 2 3 24001 13 14 25001 5 4 26001 19 20...
output:
1 2 3 4 3 4 5 6 7 6 7 8 9 8 7 8 9 10 11 10 9 8 9 10 11 12 13 14 15 14 13 12 11 10 11 12 11 12 13 12 11 12 11 12 11 12 13 12 11 12 11 10 11 12 13 14 13 14 13 12 11 12 13 12 11 12 13 12 13 12 11 12 13 12 13 14 15 16 15 14 13 12 13 14 13 12 13 14 15 16 17 16 15 16 15 14 15 14 15 14 15 14 15 14 13 14 15...
result:
ok 200000 lines
Test #28:
score: 0
Accepted
time: 1020ms
memory: 11384kb
input:
20 200000 200000 1 16 17 1201 18 19 2401 5 6 3601 13 12 4801 9 10 6001 11 12 7201 16 17 8401 12 13 9601 6 7 10801 17 16 12001 2 1 13201 2 3 14401 2 3 15601 13 14 16801 6 7 18001 16 17 19201 11 10 20401 11 10 21601 13 14 22801 12 13 24001 11 12 25201 19 20 26401 12 13 27601 15 16 28801 6 7 30001 9 8 ...
output:
1 2 3 4 5 6 5 4 5 6 7 8 7 8 7 6 7 6 5 6 5 6 5 6 7 8 7 8 7 8 7 8 9 10 11 10 11 10 9 10 11 12 13 12 11 12 11 12 13 12 13 14 15 14 13 14 13 14 13 14 13 12 13 14 15 16 15 14 13 14 15 14 13 14 13 14 15 16 15 14 15 16 15 14 13 12 13 14 13 14 15 16 17 16 17 16 15 16 17 16 17 16 15 16 15 16 17 16 15 16 15 1...
result:
ok 200000 lines
Test #29:
score: 0
Accepted
time: 1032ms
memory: 11408kb
input:
20 200000 200000 1 3 2 1401 18 17 2801 8 7 4201 14 15 5601 7 6 7001 8 7 8401 9 8 9801 6 7 11201 3 4 12601 14 13 14001 19 20 15401 3 2 16801 17 16 18201 10 9 19601 17 18 21001 9 8 22401 7 6 23801 18 19 25201 12 11 26601 7 8 28001 14 15 29401 10 11 30801 14 15 32201 14 13 33601 4 5 35001 9 10 36401 10...
output:
1 2 3 4 5 4 5 6 7 8 9 8 9 10 9 8 7 8 9 10 9 10 11 10 11 12 11 12 11 12 13 14 15 14 13 14 13 12 11 12 11 12 13 14 15 16 15 14 15 14 13 14 15 14 15 16 15 14 13 14 15 14 15 14 15 14 15 16 17 16 15 16 15 16 15 16 17 18 17 18 17 18 17 16 15 16 15 16 17 16 17 16 15 16 17 16 17 18 17 18 19 18 17 18 17 18 1...
result:
ok 200000 lines
Test #30:
score: 0
Accepted
time: 938ms
memory: 11632kb
input:
20 200000 200000 1 13 12 1601 9 8 3201 14 15 4801 16 15 6401 1 2 8001 14 15 9601 2 1 11201 13 12 12801 7 8 14401 4 3 16001 15 16 17601 5 4 19201 4 3 20801 5 6 22401 2 3 24001 12 11 25601 8 7 27201 8 7 28801 5 6 30401 4 5 32001 15 16 33601 10 11 35201 6 5 36801 9 10 38401 7 8 40001 10 11 41601 14 13 ...
output:
1 2 3 4 5 4 3 2 3 4 5 6 5 6 7 8 7 8 7 8 7 8 9 10 9 8 9 10 11 10 9 10 11 10 9 10 9 8 9 10 9 10 11 12 13 12 11 12 11 10 11 12 13 12 11 10 11 10 9 10 11 12 13 12 13 12 11 12 11 12 11 12 11 10 11 10 11 10 11 10 11 12 11 10 9 10 9 10 9 10 11 12 11 10 11 10 11 12 11 12 13 12 11 10 11 12 13 14 13 12 11 12 ...
result:
ok 200000 lines