QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#375713#5116. ContestsWorld_CreaterWA 4ms10152kbC++141.7kb2024-04-03 15:07:162024-04-03 15:07:17

Judging History

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

  • [2024-04-03 15:07:17]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:10152kb
  • [2024-04-03 15:07:16]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,m,q,f[6][100005][17],a[6][100005],rk[6][100005];
int nw[6],nxt[6];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>a[i][j];
			rk[i][a[i][j]]=j;
		}
	}
	for(int i=1;i<=m;i++)
	{
		memset(nw,0,sizeof(nw));
		for(int j=n;j>=1;j--)
		{
			for(int k=1;k<=m;k++)
			{
				if(nw[k]==0||rk[k][a[i][j]]<rk[k][nw[k]])
				{
					nw[k]=a[i][j];
				}
			}
			for(int k=1;k<=m;k++)
			{
				if(f[k][a[i][j]][0]==0||rk[k][nw[k]]<rk[k][f[k][a[i][j]][0]]) f[k][a[i][j]][0]=nw[k];
			}
		}
	}
	for(int i=1;(1<<i)<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=1;k<=m;k++)
			{
				f[k][j][i]=f[k][j][i-1];
				for(int t=1;t<=m;t++)
				{
					if(rk[f[k][f[t][j][i-1]][i-1]]<rk[f[k][j][i]]) f[k][j][i]=f[k][f[t][j][i-1]][i-1];
				}
				// cerr<<i<<" "<<j<<" "<<k<<" "<<f[k][j][i]<<"\n";
			}
		}
	}
	cin>>q;
	while(q--)
	{
		int x,y;
		cin>>x>>y;
		if(x==y)
		{
			cout<<0<<"\n";
			continue ;
		}
		bool fl=0;
		for(int i=1;i<=m;i++)
		{
			if(rk[i][x]<rk[i][y])
			{
				cout<<"1\n";
				fl=1;
				break ;
			}
		}
		if(fl) continue ;
		int ans=0;
		for(int i=1;i<=m;i++)
		{
			nw[i]=x;
		}
		for(int i=__lg(n);i>=0;i--)
		{
			memset(nxt,0,sizeof(nxt));
			for(int j=1;j<=m;j++)
			{
				for(int k=1;k<=m;k++)
				{
					if(nxt[k]==0||rk[k][f[k][nw[j]][i]]<rk[k][nxt[k]])
					{
						nxt[k]=f[k][nw[j]][i];
					}
				}
			}
			bool fl=0;
			for(int j=1;j<=m;j++)
			{
				if(rk[j][nxt[j]]<rk[j][y]) fl=1;
			}
			if(!fl)
			{
				ans+=1<<i;
				memcpy(nw,nxt,sizeof(nxt));
			}
		}
		cout<<ans+2<<"\n";
	}
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 7724kb

input:

6 2
1 3 2 5 4 6
2 1 4 3 6 5
4
1 4
5 3
6 1
5 2

output:

1
2
5
3

result:

ok 4 number(s): "1 2 5 3"

Test #2:

score: -100
Wrong Answer
time: 4ms
memory: 10152kb

input:

998 5
1 2 6 3 4 5 7 11 8 9 14 12 13 10 15 16 18 19 20 17 23 22 21 26 24 25 27 29 30 28 32 31 34 33 37 38 39 35 40 36 41 43 42 46 44 48 45 47 51 49 50 56 52 57 53 54 55 62 58 59 63 64 60 65 66 61 67 69 70 68 71 73 74 75 72 78 77 79 82 76 81 85 84 80 86 87 83 88 90 91 89 92 96 98 94 95 97 101 93 103 1...

output:

94
1025
1
1
1
21
1
154
1025
1
19
1025
25
1
1
1
80
1
1
1
1
1025
1
36
102
1
1
1
30
92
1
1
1025
37
36
60
1
1
1
1
1
1
1
1
16
1025
1025
1
1
1025
1025
1
1
142
1
1
77
1
60
1
1
1
4
90
1
1
1025
36
93
1
1
17
148
1
1
1
136
1025
1025
1
28
1025
1025
32
182
1
1025
1025
1
1
1
56
1025
75
25
115
122
1
1025
1
1
2
1
1...

result:

wrong answer 2nd numbers differ - expected: '-1', found: '1025'