QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#644088	#5116. Contests	Green_Hand	AC ✓	250ms	62068kb	C++20	1.9kb	2024-10-16 10:48:14	2024-10-16 10:48:20

Judging History

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

[2024-10-16 10:48:20]
评测

测评结果：AC
用时：250ms
内存：62068kb

查看

[2024-10-16 10:48:14]
提交

answer

#include <cstdio>
#include <cstring>
using namespace std;

const int N = 1E5 + 7, M = 7;
int n,m,q,log[N],a[M][N],pos[M][N],f[N][M][20],g[M],tmp[M];

void minn(int &x,int y) { y < x && (x = y); }

void read(int &x)
{
	char c = getchar(); x = 0;
	while(c < '0' || c > '9') c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
}

int main()
{
	read(n), read(m), log[0] = -1;
	for(int i = 1;i <= n; ++ i) log[i] = log[i >> 1] + 1;
	
	for(int i = 1;i <= m; ++ i)
		for(int j = 1;j <= n; ++ j)
			read(a[i][j]), pos[i][a[i][j]] = j, f[a[i][j]][i][0] = j;
	
	for(int i = 1,mi[M];i <= m; ++ i)
	{
		for(int k = 1;k <= m; ++ k) mi[k] = n + 1;
		
		for(int j = n;j >= 1; -- j)
		{
			for(int k = 1;k <= m; ++ k) minn(f[a[i][j]][k][0],mi[k]);
			for(int k = 1;k <= m; ++ k) minn(mi[k],pos[k][a[i][j]]);
		}
	}
	
	for(int k = 1;k <= log[n]; ++ k)
		for(int i = 1;i <= n; ++ i)
			for(int j = 1;j <= m; ++ j)
			{
				f[i][j][k] = f[i][j][k - 1];
				for(int l = 1;l <= m; ++ l)
					minn(f[i][j][k],f[a[l][f[i][l][k - 1]]][j][k - 1]);
			}
	
	read(q);
	for(int x,y,flag,ans;q--;)
	{
		read(x), read(y), ans = flag = 0;
		
		for(int i = 1;i <= m; ++ i) flag |= pos[i][x] < pos[i][y];
		if(flag) { printf("1\n"); continue; }
		
		for(int i = 1;i <= m; ++ i) g[i] = pos[i][x];
		for(int k = log[n];k >= 0; -- k)
		{
			flag = 0;
			for(int i = 1;i <= m; ++ i)
			{
				tmp[i] = g[i];
				for(int j = 1;j <= m; ++ j)
					minn(tmp[i],f[a[j][g[j]]][i][k]);
				if(tmp[i] < pos[i][y]) flag = 1;
			}
			if(flag) continue;
			
			for(int i = 1;i <= m; ++ i) g[i] = tmp[i];
			ans |= 1 << k;
		}
		
		flag = 0;
		for(int i = 1;i <= m; ++ i)
		{
			tmp[i] = g[i];
			for(int j = 1;j <= m; ++ j)
				minn(tmp[i],f[a[j][g[j]]][i][0]);
			if(tmp[i] < pos[i][y]) flag = 1;
		}
		printf("%d\n",flag ? ans + 2 : -1);
	}
	
	return 0;
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 5576kb

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:

result:

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

Test #2:

score: 0

Accepted

time: 2ms

memory: 8192kb

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:

result:

ok 1000 numbers

Test #3:

score: 0

Accepted

time: 155ms

memory: 61668kb

input:

99997 5
13846 76247 14430 82900 22678 13000 88476 33335 50407 77862 3545 90269 94531 98082 56502 14027 27673 54173 42855 59901 40095 36046 32844 88104 38879 84883 45979 3117 80875 18985 43692 81119 8682 6390 99780 18979 73738 26817 37612 38509 34976 81565 9953 33844 61610 17678 38492 57218 96547 157...

output:

result:

ok 99998 numbers

Test #4:

score: 0

Accepted

time: 164ms

memory: 61648kb

input:

99997 5
64625 15368 86064 79628 49377 9409 53118 61183 39656 22147 23771 67307 29014 79512 84377 58635 22778 53648 4152 26331 30475 34473 93457 71345 50206 78514 10202 79575 95432 58462 32326 57380 93587 91341 33160 73433 41107 82641 9128 5017 12999 59528 75815 4202 27655 3280 4141 54932 34121 38658...

output:

result:

ok 99998 numbers

Test #5:

score: 0

Accepted

time: 161ms

memory: 61660kb

input:

99997 5
58514 57682 42105 43145 8158 20242 20371 16614 7432 98349 48955 1535 4647 61696 36695 33096 46689 30136 6830 55342 96730 39847 58695 2068 18778 68294 47448 19033 30216 24916 41318 40936 31337 47955 76457 32267 52220 62105 4457 9621 77701 4356 9567 70502 10743 93158 96758 72007 65570 69266 42...

output:

result:

ok 99998 numbers

Test #6:

score: 0

Accepted

time: 159ms

memory: 61652kb

input:

99997 5
12123 79135 7559 8378 73864 21681 29911 71042 91841 13981 9981 45225 28803 66972 74201 42242 38116 88036 31114 89177 39353 46329 26445 76354 87347 27193 23943 17744 60549 17213 227 99561 22027 77161 66720 30489 11161 88192 34007 31368 89832 10883 78161 7264 1328 32989 7519 61525 28614 96023 ...

output:

result:

ok 99998 numbers

Test #7:

score: 0

Accepted

time: 157ms

memory: 61664kb

input:

99997 5
18291 50708 25258 22267 24292 80896 48412 10059 76253 78698 79475 71080 94605 70762 26399 46328 38921 21637 21059 692 10980 19770 43518 86172 40349 51705 30507 9704 11265 22490 34825 5209 18337 2623 86178 95377 39724 31360 70797 53882 47298 34237 18673 30555 33241 26670 11605 80604 69497 842...

output:

result:

ok 99998 numbers

Test #8:

score: 0

Accepted

time: 35ms

memory: 61964kb

input:

99998 1
70242 55692 47154 96102 27579 6889 66745 92632 39813 25663 25647 53493 39170 27398 6217 37894 32165 15352 43981 75150 37853 79002 35076 78592 54779 29726 14716 24896 1890 78236 52141 75129 72669 1162 92653 70522 18962 30745 48956 88916 84086 43644 45589 33178 29088 71530 41141 65654 96266 80...

output:

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
-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...

result:

ok 99998 numbers

Test #9:

score: 0

Accepted

time: 81ms

memory: 60792kb

input:

99998 2
1232 10275 24682 16281 28152 77383 43082 89941 11688 42775 48409 9975 3379 53549 6489 40458 8024 69107 68970 14412 19266 94330 81431 63859 59906 94754 80796 88757 47279 41080 18941 24750 2633 25730 83880 15169 89377 74186 82300 86350 79673 97777 4524 55193 24673 58950 21852 24494 82330 78333...

output:

result:

ok 99997 numbers

Test #10:

score: 0

Accepted

time: 172ms

memory: 61624kb

input:

99998 5
54008 95524 29471 66271 94736 32118 79141 2082 51062 18278 39625 67650 28196 85028 21148 53512 34590 29622 71446 21297 76872 78414 55058 360 48522 42817 53133 25085 14356 6384 94059 32196 49192 48615 36171 48245 51010 83685 54394 21025 44250 436 12628 12015 20154 71524 77348 43435 51325 2694...

output:

result:

ok 100000 numbers

Test #11:

score: 0

Accepted

time: 146ms

memory: 62052kb

input:

99998 4
78352 87432 79198 30861 44306 82951 31679 65868 3843 51726 65285 4319 98442 83829 12182 15883 32075 47286 75186 5064 78210 23240 95711 84279 90981 84087 73533 72896 16695 95190 21357 91792 27018 48281 37681 45566 69622 89413 43385 49519 27900 85867 76477 18139 7451 28916 8873 93859 41355 776...

output:

result:

ok 99998 numbers

Test #12:

score: 0

Accepted

time: 123ms

memory: 62064kb

input:

99998 3
5851 87228 10732 76764 90049 52970 96057 29181 36694 89924 90474 10409 66246 77106 20546 4488 68960 1015 40533 50001 59277 78134 28267 54082 31429 17894 44422 70464 14516 30060 80440 45305 29630 72921 22709 9719 34972 22703 8464 68919 35713 81493 36612 90600 31301 39578 45928 21441 86719 120...

output:

result:

ok 99999 numbers

Test #13:

score: 0

Accepted

time: 136ms

memory: 61484kb

input:

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

output:

1
1
1
-1
-1
-1
18
-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
-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...

result:

ok 100000 numbers

Test #14:

score: 0

Accepted

time: 96ms

memory: 62068kb

input:

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

output:

result:

ok 99999 numbers

Test #15:

score: 0

Accepted

time: 66ms

memory: 61672kb

input:

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

output:

-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
-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
...

result:

ok 99999 numbers

Test #16:

score: 0

Accepted

time: 25ms

memory: 62040kb

input:

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

output:

-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
-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...

result:

ok 100000 numbers

Test #17:

score: 0

Accepted

time: 201ms

memory: 61632kb

input:

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

output:

result:

ok 100000 numbers

Test #18:

score: 0

Accepted

time: 250ms

memory: 61760kb

input:

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

output:

result:

ok 99999 numbers