QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#14923	#2019. 移球游戏	JohnAlfnov	100 ✓	65ms	10364kb	C++98	2.0kb	2021-10-27 13:48:51	2022-05-17 01:15:31

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:15:31]
评测

测评结果：100
用时：65ms
内存：10364kb

查看

[2021-10-27 13:48:51]
提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,m,a[55][405],vist[55],tot=0,b1[820005],b2[820005],f[55][405],ss[55];
stack<int>st[55];
void gb(int x,int y)
{
	int t3=tot+1;
	stack<int>s1,s2,s3;
	for(int i=1;i<=m;i++)s1.push(a[x][i]),s2.push(a[y][i]);
	int s=0,js=10000;
	for(int i=1;i<=m;i++)js=min(js,min(a[x][i],a[y][i]));
	for(int i=1;i<=m;i++)if(a[x][i]==js)s++;
	for(int i=1;i<=s;i++)b1[++tot]=y,b2[tot]=n+1,s3.push(s2.top()),s2.pop();
	for(int i=m;i>=1;i--)
	{
		if(a[x][i]==js)
			b1[++tot]=x,b2[tot]=y,s2.push(s1.top()),s1.pop();
		else b1[++tot]=x,b2[tot]=n+1,s3.push(s1.top()),s1.pop();
	}
	for(int i=1;i<=m;i++)b1[++tot]=y,b2[tot]=x,s1.push(s2.top()),s2.pop();
	for(int i=1;i<=m-s;i++)b1[++tot]=n+1,b2[tot]=y,s2.push(s3.top()),s3.pop();
	for(int i=1;i<=m-s;i++)b1[++tot]=x,b2[tot]=n+1,s3.push(s1.top()),s1.pop();
	for(int i=1;i<=m;i++)
	{
		if(s1.size()==m)
			vist[x]=1,b1[++tot]=n+1,b2[tot]=y,s2.push(s3.top()),s3.pop();
		else if(s2.size()==m)
			vist[y]=1,b1[++tot]=n+1,b2[tot]=x,s1.push(s3.top()),s3.pop();
		else if(s3.top()==js)
			b1[++tot]=n+1,b2[tot]=x,s1.push(s3.top()),s3.pop();
		else b1[++tot]=n+1,b2[tot]=y,s2.push(s3.top()),s3.pop();
	}
	ss[n+1]=0;
	ss[x]=ss[y]=m;
	for(int i=t3;i<=tot;i++)f[b2[i]][++ss[b2[i]]]=f[b1[i]][ss[b1[i]]--];
}
void merge(int l,int r)
{
	if(l==r)return;
	for(int i=l;i<=r;i++)vist[i]=0;
	int mid=l+r>>1;
	for(int i=l;i<=r;i++)for(int j=1;j<=m;j++)
	{
		if(f[i][j]<=mid)a[i][j]=1;
		else a[i][j]=2;
	}
	int l1=l,l2=mid+1;
	while(l1<=mid&&l2<=r)
	{
		gb(l1,l2);
		for(int i=1;i<=m;i++)
		{
			if(f[l1][i]<=mid)a[l1][i]=1;
			else a[l1][i]=2;
			if(f[l2][i]<=mid)a[l2][i]=1;
			else a[l2][i]=2;
		}
		if(vist[l1])l1++;
		if(vist[l2])l2++;
	}
	merge(l,mid);
	merge(mid+1,r);
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
		scanf("%d",&a[i][j]),f[i][j]=a[i][j];
	merge(1,n);
	cout<<tot<<endl;
	for(int i=1;i<=tot;i++)printf("%d %d\n",b1[i],b2[i]);
	return 0;
}

Source code, Language: C++98

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5

Accepted

time: 0ms

memory: 6000kb

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

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

memory: 5972kb

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

memory: 5980kb

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

memory: 6028kb

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

memory: 6444kb

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

memory: 6356kb

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

memory: 8136kb

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

memory: 10328kb

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

memory: 10268kb

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

memory: 9192kb

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

memory: 9352kb

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

memory: 10364kb

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

memory: 8480kb

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

memory: 9284kb

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

memory: 9832kb

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

memory: 10076kb

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

memory: 9272kb

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

memory: 8872kb

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

memory: 8720kb

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