QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#290637	#2019. 移球游戏	MoRanSky	100 ✓	31ms	10224kb	C++23	1.7kb	2023-12-25 06:13:46	2023-12-25 06:13:47

Judging History

你现在查看的是最新测评结果

[2023-12-25 06:13:47]
评测

测评结果：100
用时：31ms
内存：10224kb

查看

[2023-12-25 06:13:46]
提交

answer

#include <iostream>
#include <cstdio>
#define is(x) (o ? x > mid : x <= mid)
using namespace std;

const int N = 55, M = 405, S = 820005;

int n, m, a[N][M], len[M], X[S], Y[S], tot, b[N], c1[N], c2[N], e;

void inline add(int x, int y) {
	X[++tot] = x, Y[tot] = y;
	a[y][++len[y]] = a[x][len[x]--];
}

int inline work(int u, int v, int mid) {
	int cnt = 0, o = 0;
	for (int i = 1; i <= m; i++)
		cnt += (a[u][i] <= mid) + (a[v][i] <= mid);
	if (cnt < m) o = 1;
	int s = 0;
	for (int i = 1; i <= m; i++) {
		s += is(a[u][i]);
	}
	for (int i = 1; i <= s; i++) add(v, e);
	for (int i = 1; i <= m; i++) {
		if (is(a[u][len[u]])) add(u, v);
		else add(u, e);
	}
	for (int i = 1; i <= m; i++) add(v, u);
	for (int i = 1; i <= m - s; i++) add(e, v);
	for (int i = 1; i <= m - s; i++) add(u, e);
	for (int i = 1; i <= m; i++) {
		if (is(a[e][len[e]]) && len[u] < m) add(e, u);
		else add(e, v);
	}
	return o;
}

void solve(int l, int r, int L, int R) {
	if (l >= r) return;
	int mid = (L + R) >> 1;
	int t1 = 0, t2 = 0;
	for (int i = l; i < r; i++) {
		if (work(b[i], b[r], mid)) c2[++t2] = b[i];
		else c1[++t1] = b[i]; 
	}
	if (a[b[r]][1] <= mid) c1[++t1] = b[r];
	else c2[++t2] = b[r];
	for (int i = 1; i <= t1; i++)
		b[l + i - 1] = c1[i];
	for (int i = 1; i <= t2; i++)
		b[l + t1 + i - 1] = c2[i];
	solve(l, l + t1 - 1, L, mid);
	solve(l + t1, r, mid + 1, R);
}

int main() {
	scanf("%d%d", &n, &m); e = n + 1;
	for (int i = 1; i <= n; i++) {
		b[i] = i, len[i] = m;
		for (int j = 1; j <= m; j++) {
			scanf("%d", &a[i][j]);
		}
	}
	solve(1, n, 1, n);
	printf("%d\n", tot);
	for (int i = 1; i <= tot; i++) {
		printf("%d %d\n", X[i], Y[i]);
	}
	return 0;
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5

Accepted

time: 1ms

memory: 5980kb

input:

2 20
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1

output:

result:

ok OK

Test #2:

score: 5

Accepted

time: 1ms

memory: 5972kb

input:

2 20
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 2 1

output:

result:

ok OK

Test #3:

score: 5

Accepted

time: 1ms

memory: 6004kb

input:

10 20
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 4 7 2 9
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 10 3 4 1 5
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 9 7 7 4 6
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 10 3 7 6 5
7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 2 3 1 2 5
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 6 9 10 8 9
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 2 1 4...

output:

result:

ok OK

Test #4:

score: 5

Accepted

time: 0ms

memory: 5812kb

input:

10 20
7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 1
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 8 2 3 2 9
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 8 1 8 1
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 4 9 6 10 2
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 9 10 4 3 9
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 4 7 6 5
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 10 2 1 ...

output:

result:

ok OK

Test #5:

score: 5

Accepted

time: 1ms

memory: 5808kb

input:

10 20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4 6 1 6 8
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 9 2 1 10 3
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 9 8 7 3 9
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 8 9 2 2 2
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 10 4 5 3 8
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 1 3 10 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 6 2 1
7 7 7 7 7 7...

output:

result:

ok OK

Test #6:

score: 5

Accepted

time: 7ms

memory: 6324kb

input:

50 85
34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 32 21 34 48 29 15 10 26 23 10 30 39 29 11 37 10 20 4 26 8 30 33 19 45 43 3 28 30 2 49 43 30 26 10 12 28 27 1 18 38 27 21 48 32 38 11 14 31 29 31 41 28 44 1 11 26 25 34 21 1 50 26 23 43 44 26 1 50 38 31
36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36...

output:

result:

ok OK

Test #7:

score: 5

Accepted

time: 3ms

memory: 8352kb

input:

50 85
13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 44 35 37 50 30
19 19 19 19 19 19 19 19 19 19 19 19 19 ...

output:

result:

ok OK

Test #8:

score: 5

Accepted

time: 7ms

memory: 8300kb

input:

50 85
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 28 46 38 39 49 21 39 7 17 18 34 2 34 39 3 44 42 21 20 18 21 30 8 21 28 13 31 18 37 5 5 46 25 11 32 7 22 39 6 3 22 31 36 33 17 15 19 22 42 33 14 47 47 42 3 49 50 31 20 34 43 33 13 14 6 24 2 18 35 31
23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 32 34 ...

output:

result:

ok OK

Test #9:

score: 5

Accepted

time: 23ms

memory: 8608kb

input:

50 300
28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 2 35 41 4 35 30 2 10 16 36 2 34 10 36 32 18 11 23 47 22 16 10 20 12 10 10 7 39 14 40 3 1 26 23 22 12 47 34 45 48 50 33 11 11 18 30 14 15 16 39 37 14 6 33 34 23 18 21 45 32 16 5 20 29 15 28 8 3 8 35 10 39 4 40 16 13 38 38 16 9 2 38 22 14 3 14 16 42 ...

output:

result:

ok OK

Test #10:

score: 5

Accepted

time: 23ms

memory: 9084kb

input:

50 300
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 26 48 48 49 45 48 4 10 27 19 50 30 24 16 9 41 14 19 19 41 15 7 17 27 30 12 4 45 20 7 35 17 50 37 15 18 50 5 48 49 2 7 11 34 9 38 10 21 39 35 45 6 50 2 28 2 48 38 2 16 39 38 3 32 20 10 14 41 28 7 2 4 35 2 45 15 38 2 26 41 36 46 4 15 38 21 9 18 49 7 6 15 32 11 36 3...

output:

result:

ok OK

Test #11:

score: 5

Accepted

time: 23ms

memory: 8708kb

input:

50 300
7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 37 15 25 13 21 35 45 26 26 48 20 38 13 35 15 33 8 16 16 33 1 27 48 12 22 6 48 5 30 26 4 12 28 22 42 45 39 27 21 11 10 35 6 7 1 37 29 48 14 18 46 4 13 1 18 14 42 41 40 46 6 8 4 8 38 20 26 13 25 25 32 22 18 22 45 1 27 23 40 25 16 4 43 16 26 43 49 23 26 14 4 35 23 2...

output:

result:

ok OK

Test #12:

score: 5

Accepted

time: 16ms

memory: 8984kb

input:

50 300
20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 44 16 43 44 28 25 21 33 12 1 26 22 25 16 4 47 20 32 20 26 40 23 47 27 9 20 19 32 44 8 18 25 11 34 20 23 21 22 34 21 12 1 32 49 36 39 45 44 32 46 36 45 43 44 12 6 12 33 32 38 41 26 12 28 30 30 24 33 26 43 14 1 5 25 19 41 12 33 45 40 18 22 30 8 1 4 3...

output:

result:

ok OK

Test #13:

score: 5

Accepted

time: 23ms

memory: 8892kb

input:

50 300
7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 39 15 50 10 9 11 33 24 7 29 31 32 24 50 19 25 18 4 19 40 38 9 6 22 18 50 25 28 50 26 48 15 44 14 4 45 25 42 3 27 29 38 18 44 35 31 43 40 41 10 2 7 25 25 8 33 43 5 12 34 4 44 27 24 49 45 50 32 41 9 3 6 8 48 9 19 44 45 48 40 29 16 38 26 16 38 14 3 6 44 3 38 49 28 3...

output:

result:

ok OK

Test #14:

score: 5

Accepted

time: 23ms

memory: 9168kb

input:

50 300
12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 26 26 32 15 40 24 49 16 2 35 20 19 23 12 50 44 21 2 2 48 38 8 12 30 41 19 10 2 10 33 4 42 42 3 9 25 36 24 39 31 25 11 29 34 50 30 47 17 30 48 32 4 20 50 29 37 27 22 7 42 19 25 32 2 34 31 33 3 11 5 22 50 11 23 2 19 2 20 23 19 6 29 14 16 44 29 12 20 ...

output:

result:

ok OK

Test #15:

score: 5

Accepted

time: 30ms

memory: 10200kb

input:

50 400
37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37...

output:

result:

ok OK

Test #16:

score: 5

Accepted

time: 31ms

memory: 8812kb

input:

50 400
43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 42 1 23 50 36 5 41 5 36 17 14 41 47 19 8 20 21 28 7 25 22 42 12 48 22 6 44 33 19 32 36 26 10 16 46 22 27 6 45 5 50 21 9 42 46 33 40 7 6 10 32 50 25 41 20 26 15 19 6 22 35 27 10 39 27 6 8 2 32 1 25 4 25 25 13 35 3 20 31 17 37 25 14 12 33 29 31 4 27 ...

output:

result:

ok OK

Test #17:

score: 5

Accepted

time: 31ms

memory: 9240kb

input:

50 400
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 25 27 49 4 5 27 9 42 20 43 37 12 22 1 17 34 8 29 6 39 30 30 49 9 22 33 23 31 38 2 30 24 36 42 5 45 39 28 22 3 23 22 16 46 48 48 8 45 17 49 7 40 21 5 39 39 27 41 9 15 20 4 23 5 2 35 20 43 38 28 40 7 48 49 50 31 6 16 41 38 20 47 49 29 29 8 48 4 25 39 16 24 19 21 9 ...

output:

result:

ok OK

Test #18:

score: 5

Accepted

time: 27ms

memory: 8812kb

input:

50 400
25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 47 5 39 47 4 16 43 19 34 45 25 26 50 1 25 41 46 25 40 29 29 49 15 33 46 35 3 11 20 27 15 6 41 1 18 2 43 41 9 19 13 34 38 20 4 2 13 11 4 36 14 40 32 49 20 14 48 21 39 48 43 3 33 8 3 3 29 32 23 10 37 42 32 11 39 50 12 9 28 3 33 30 20 16 18 45 4 21 37...

output:

result:

ok OK

Test #19:

score: 5

Accepted

time: 24ms

memory: 10224kb

input:

50 400
50 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50...

output:

result:

ok OK

Test #20:

score: 5

Accepted

time: 29ms

memory: 9524kb

input:

50 400
50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

result:

ok OK

Extra Test:

score: 0

Extra Test Passed