QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#14884	#2019. 移球游戏	123456	100 ✓	60ms	8940kb	C++20	1.7kb	2021-10-21 11:31:49	2022-05-17 01:11:03

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-05-17 01:11:03]
评测

测评结果：100
用时：60ms
内存：8940kb

查看

[2021-10-21 11:31:49]
提交

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);
			if(s>=m) //<=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;
			}
			else //>mid
			{
				s=0;for(int k=1;k<=m;k++) s+=(a[j][k]>mid);
				for(int k=1;k<=s;k++) pour(i,n+1); //1
				while(top[j]) a[j][top[j]]>mid?pour(j,i):pour(j,n+1); //2
				for(int k=1;k<=s;k++) pour(i,j);
				for(int k=1;k<=m-s;k++) pour(n+1,j);
				for(int k=1;k<=m-s;k++) pour(i,n+1); //3
				for(int k=1;k<=m-s;k++) pour(j,i); //4
				while(top[n+1]) 
				{
					if(top[j]==m || a[n+1][top[n+1]]<=mid) pour(n+1,i);
					else pour(n+1,j); 
				}
				flag[j]=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

Test #1:

score: 5

Accepted

time: 3ms

memory: 3744kb

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

memory: 3804kb

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

memory: 5896kb

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

memory: 5832kb

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

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:

ok OK

Test #6:

score: 5

Accepted

time: 12ms

memory: 4496kb

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

memory: 6168kb

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

memory: 4456kb

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

memory: 7360kb

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

memory: 7016kb

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

memory: 7676kb

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

memory: 7616kb

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

memory: 6600kb

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

memory: 7384kb

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

memory: 7060kb

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

memory: 8940kb

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

memory: 8828kb

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

memory: 7072kb

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

memory: 7476kb

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

memory: 6748kb

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