QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#790671	#2019. 移球游戏	_LSA_	100 ✓	38ms	9468kb	C++20	2.3kb	2024-11-28 14:33:16	2024-11-28 14:33:17

Judging History

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

[2024-11-28 14:33:17]
评测

测评结果：100
用时：38ms
内存：9468kb

查看

[2024-11-28 14:33:16]
提交

answer

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
#define ull unsigned ll
using namespace std;
ll read(){
	ll X = 0,r = 1;
	char ch = getchar();
	while(!isdigit(ch) && ch != '-') ch = getchar();
	if(ch == '-') r = -1,ch = getchar();
	while(isdigit(ch)) X = X*10+ch-'0',ch = getchar();
	return X*r;
}
const int N = 55;
const int M = 410;
int n,m;
int a[N][M],top[N],p[N];
vector<pii> ans;
void move(int x,int y){
	ans.emplace_back(x,y);
//	cout << x << " " << y << "\n";
	assert(top[x] >= 1);
	a[y][++top[y]] = a[x][top[x]];
	a[x][top[x]--] = 0;
}
bool flag[N];
void solve(int l,int r){
	if(l == r) return ;
	int mid = (l+r) >> 1;
	for(int i=l;i<=r;i++) flag[i] = 0;
	for(int I=l;I<=mid;I++) for(int J=mid+1;J<=r;J++){
		if(flag[I] || flag[J]) continue;
		int i = p[I],j = p[J],q = p[n+1];
		int sum = 0;
		for(int k=1;k<=m;k++) sum += a[i][k] <= mid;
		for(int k=1;k<=m;k++) sum += a[j][k] <= mid;
		if(sum >= m){
			sum = 0;
			for(int k=1;k<=m;k++) sum += a[i][k] <= mid;
			for(int k=1;k<=m-sum;k++) move(j,q);
			for(int k=m;k;k--)
				if(a[i][k] <= mid) move(i,q);
				else move(i,j);
			for(int k=1;k<=sum;k++) move(q,i);
			for(int k=1;k<=m-sum;k++) move(j,i);
			while(top[q]) move(q,j);
			for(int k=1;k<=m-sum;k++) move(i,q);
			for(int k=m;k;k--)
				if(a[j][k] <= mid&&top[i]<m) move(j,i);
				else move(j,q);
			swap(p[J],p[n+1]);
			flag[I] = true;
		}else{
			sum = 0;
			for(int k=1;k<=m;k++) sum += a[j][k] > mid;
			for(int k=1;k<=m-sum;k++) move(i,q);
			for(int k=m;k;k--)
				if(a[j][k] > mid) move(j,q);
				else move(j,i);
			for(int k=1;k<=sum;k++) move(q,j);
			for(int k=1;k<=m-sum;k++) move(i,j);
			while(top[q]) move(q,i);
			for(int k=1;k<=m-sum;k++) move(j,q);
			for(int k=m;k;k--)
				if(a[i][k] > mid&&top[j]<m) move(i,j);
				else move(i,q);
			swap(p[I],p[n+1]);
			flag[J] = true;
		}
	}
	solve(l,mid); solve(mid+1,r);
}
int main(){
//	freopen("ball.in","r",stdin);
//	freopen("ball.out","w",stdout);
	n = read(); m = read();
	for(int i=1;i<=n+1;i++) p[i] = i;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) a[i][j] = read();
		top[i] = m;
	}
	solve(1,n);
	cout << ans.size() << "\n";
	for(auto it : ans) cout << it.fi << " " << it.se << "\n";
	return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Pretests

Final Tests

Test #1:

score: 5

Accepted

time: 0ms

memory: 3620kb

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: 0ms

memory: 3584kb

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: 3684kb

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: 1ms

memory: 3764kb

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: 3660kb

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: 8ms

memory: 4244kb

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: 8ms

memory: 4272kb

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: 8ms

memory: 4200kb

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: 25ms

memory: 9228kb

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: 24ms

memory: 9200kb

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: 29ms

memory: 8892kb

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: 24ms

memory: 9156kb

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: 29ms

memory: 9160kb

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: 24ms

memory: 8952kb

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: 37ms

memory: 7952kb

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: 34ms

memory: 9240kb

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: 37ms

memory: 8688kb

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: 33ms

memory: 7868kb

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: 38ms

memory: 9468kb

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: 26ms

memory: 8664kb

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