QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#790564	#2019. 移球游戏	_LSA_	10	19ms	7636kb	C++20	1.2kb	2024-11-28 13:31:23	2024-11-28 13:31:25

Judging History

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

[2024-11-28 13:31:25]
评测

测评结果：10
用时：19ms
内存：7636kb

查看

[2024-11-28 13:31:23]
提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=55,M=405,K=820005;
int a[N][M],top[N],n,m,ans[K][2],tot;bool flag[N];
inline void pour(int x,int y) 
{
	ans[++tot][0]=x,ans[tot][1]=y;
	a[y][++top[y]]=a[x][top[x]--];
}
void solve(int l,int r)
{
	if(l==r) return;
	int mid=l+r>>1;
	memset(flag,0,sizeof(flag));
	for(int i=l;i<=mid;i++)
		for(int j=mid+1;j<=r;j++)
		{
			if(flag[i] || flag[j]) continue;
			int s=0;for(int k=1;k<=m;k++) s+=(a[i][k]<=mid);
			for(int k=1;k<=m;k++) s+=(a[j][k]<=mid);
			s=0;for(int k=1;k<=m;k++) s+=(a[i][k]<=mid);
			for(int k=1;k<=s;k++) pour(j,n+1); //1
			while(top[i]) a[i][top[i]]<=mid?pour(i,j):pour(i,n+1); //2
			for(int k=1;k<=s;k++) pour(j,i);
			for(int k=1;k<=m-s;k++) pour(n+1,i);
			for(int k=1;k<=m-s;k++) pour(j,n+1); //3
			for(int k=1;k<=m-s;k++) pour(i,j); //4
			while(top[n+1]) 
			{
				if(top[i]==m || a[n+1][top[n+1]]>mid) pour(n+1,j);
				else pour(n+1,i); 
			}
			flag[i]=1;
			
		}
	solve(l,mid);solve(mid+1,r);
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) 
		for(int j=1,x;j<=m;j++)
			scanf("%d",&x),a[i][++top[i]]=x;
	solve(1,n);printf("%d\n",tot);
	for(int i=1;i<=tot;i++) printf("%d %d\n",ans[i][0],ans[i][1]);
	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: 3848kb

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

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

Wrong Answer

time: 1ms

memory: 3880kb

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:

wrong answer A 97

Test #4:

score: 0

Runtime Error

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:

Test #5:

score: 0

Wrong Answer

time: 1ms

memory: 3856kb

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:

wrong answer A 331

Test #6:

score: 0

Runtime Error

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:

Test #7:

score: 0

Runtime Error

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:

Test #8:

score: 0

Runtime Error

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:

Test #9:

score: 0

Runtime Error

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:

Test #10:

score: 0

Runtime Error

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:

Test #11:

score: 0

Runtime Error

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:

Test #12:

score: 0

Runtime Error

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:

Test #13:

score: 0

Runtime Error

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:

Test #14:

score: 0

Runtime Error

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:

Test #15:

score: 0

Runtime Error

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:

Test #16:

score: 0

Runtime Error

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:

Test #17:

score: 0

Runtime Error

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:

Test #18:

score: 0

Runtime Error

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:

Test #19:

score: 0

Runtime Error

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:

Test #20:

score: 0

Wrong Answer

time: 19ms

memory: 7636kb

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:

wrong answer A 4852