QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#290662#6235. 随机数生成器MoRanSky100 ✓767ms199164kbC++231.4kb2023-12-25 06:20:342023-12-25 06:20:35

Judging History

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

  • [2023-12-25 06:20:35]
  • 评测
  • 测评结果:100
  • 用时:767ms
  • 内存:199164kb
  • [2023-12-25 06:20:34]
  • 提交

answer

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

typedef long long LL;

const int N = 5e3 + 5;

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


int x0, a, b, c, d, p[N * N], g[N * N];

int n, m, q, tot, Lf[N], Rf[N];

bool inline check(int x, int y) {
	return y >= Rf[x - 1] && y <= Lf[x + 1]; 
}

void inline ins(int x, int y) {
	for (int i = x; i <= n; i++) Rf[i] = max(Rf[i], y);
	for (int i = x; i; i--) Lf[i] = min(Lf[i], y);
}

int main() {
	//freopen("C:/Users/MoRanSky/Downloads/random2.in", "r", stdin);
	//freopen("te.out", "w", stdout);
	memset(Lf, 0x3f, sizeof Lf);
	read(x0), read(a), read(b), read(c), read(d);
	read(n); read(m); read(q);
	int x = x0;
	for (int i = 1; i <= n * m; i++) p[i] = i;
	for (int i = 1; i <= n * m; i++) {
		x = (1ll * a * x * x + 1ll * b * x + c) % d;
		swap(p[i], p[x % i + 1]);
	}
	
	while (q--) {
		int u, v; read(u); read(v);
		swap(p[u], p[v]);
	}
	for (int i = 1; i <= n * m; i++) g[p[i]] = i;
	ins(1, 1); ins(n, m);
	for (int i = 1, x, y; i <= n * m; i++) {
		x = (g[i] - 1) / m + 1, y = (g[i] - 1) % m + 1;
		bool o = check(x, y);
		if (x + y == 2 || x + y == n + m || o) {
			if (o) ins(x, y);
			printf("%d ", i);
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 1ms
memory: 3652kb

input:

31 23 17 15 3137
7 8 0

output:

1 2 3 9 11 12 19 24 33 34 44 48 49 53 

result:

ok 14 numbers

Test #2:

score: 10
Accepted
time: 1ms
memory: 3968kb

input:

5732 32 44 550 123457
150 120 0

output:

1 3 5 7 11 13 18 25 27 41 63 72 86 113 131 137 152 162 220 242 258 323 433 459 464 507 553 718 738 746 846 862 916 1054 1058 1102 1105 1182 1184 1220 1279 1310 1320 1370 1390 1452 1467 1527 1537 1699 1723 1786 1804 1810 1862 1921 1938 1967 1979 2176 2224 2241 2451 2561 2623 2637 2669 2700 2826 2848 ...

result:

ok 269 numbers

Test #3:

score: 10
Accepted
time: 1ms
memory: 3972kb

input:

4231222 93 71901 927775 72345703
200 200 0

output:

1 2 4 7 10 25 45 51 53 77 84 85 101 106 108 114 144 165 168 181 251 264 358 417 449 470 630 649 657 664 665 684 702 704 784 836 858 863 887 986 987 1127 1153 1265 1286 1359 1438 1737 1781 1802 1918 2044 2062 2207 2436 2545 2587 2616 2634 2715 2751 2893 3255 3505 3524 3533 3599 3633 3642 3686 3704 37...

result:

ok 399 numbers

Test #4:

score: 10
Accepted
time: 95ms
memory: 34924kb

input:

1234567 197 98749347 66033937 98765441
2000 2000 16000
18041 129030
24010 2881443
24033 3054034
161252 120065
144057 1113525
96468 32036
612329 116065
8076 106219
34050 3442472
184068 1519836
108071 520016
3379879 188095
66071 459239
3924895 104093
56047 529160
3703422 88019
469187 80078
2212425 600...

output:

1 2 4 5 6 7 8 9 10 11 16 18 19 20 23 24 25 26 29 32 33 34 36 37 38 41 44 47 48 49 50 51 52 53 54 55 57 58 61 62 63 67 69 70 71 74 75 76 77 78 79 80 83 85 86 88 90 91 93 96 97 98 101 103 104 105 108 112 115 118 119 121 124 125 126 131 132 133 136 137 138 139 141 143 144 147 149 151 152 154 155 156 15...

result:

ok 3999 numbers

Test #5:

score: 10
Accepted
time: 88ms
memory: 35156kb

input:

220033 163 32964973 50146828 88265447
2000 2000 10001
42028 3259156
2123521 56005
104006 3490685
102048 1592266
132053 1567833
130019 551217
6070 2400169
36031 2979949
80006 3678634
1086862 140063
16 554706
38008 3234502
108023 1325052
1157881 112010
18052 3023143
20050 3705118
3488182 20055
779681 ...

output:

1 2 3 4 5 8 9 10 11 13 14 16 17 18 19 21 22 24 25 26 28 32 34 37 38 39 41 42 44 45 47 49 51 52 54 55 56 57 58 63 65 66 67 69 70 71 72 73 75 78 80 81 82 83 85 86 87 89 90 93 94 95 97 98 99 100 101 102 103 104 105 106 107 108 110 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 128 131 132 ...

result:

ok 3999 numbers

Test #6:

score: 10
Accepted
time: 85ms
memory: 35084kb

input:

9020033 223 61543787 95782146 98965439
2000 2000 12100
30052 2360033
2798156 66043
52052 749374
1270053 62046
316649 8
8041 171190
118045 2288631
98032 1981195
2366478 74042
118008 261327
36008 2489080
113570 42046
132047 2536642
60053 1382662
74019 2113777
80042 2268302
1691588 126002
2664888 40010...

output:

1 2 3 4 6 8 9 11 12 13 16 18 19 22 23 24 32 33 35 36 38 39 42 43 44 47 48 52 53 54 57 58 59 62 63 64 65 67 69 71 72 73 74 75 77 78 80 81 82 83 84 85 86 87 88 91 95 96 97 98 101 102 103 105 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 126 127 128 130 131 132 133 134 135 136...

result:

ok 3999 numbers

Test #7:

score: 10
Accepted
time: 767ms
memory: 198984kb

input:

7020277 176 78786360 57478061 91965439
5000 5000 23000
10524592 455097
225093 8193127
16830186 145096
65008 19729755
500057 3346073
23493254 290032
18074161 275037
405041 6927135
15512740 375017
11617444 490025
15084 21484843
20768322 55010
445013 1208799
95048 12259487
14763755 450092
365062 811007...

output:

1 3 4 5 6 7 8 10 12 14 15 16 20 21 22 23 24 25 26 27 30 33 34 36 37 38 39 40 44 45 46 47 48 50 51 54 55 56 57 58 60 61 62 65 67 69 70 71 72 73 74 75 77 78 79 81 86 87 88 89 90 91 92 93 94 95 96 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 116 118 121 122 124 125 127 128 129 131 132...

result:

ok 9999 numbers

Test #8:

score: 10
Accepted
time: 757ms
memory: 199164kb

input:

2312255 278 62630371 53301066 99995923
5000 5000 40000
24980190 320058
635001 24980191
5648562 495018
725057 8040734
325043 24980194
24206524 460093
20971572 730098
240061 12893364
480010 9389109
45040 24980199
740003 24980200
625080 12849820
24266160 745089
24980203 40145
95037 1171740
12076524 140...

output:

1 2 3 4 5 6 9 11 15 16 18 19 25 26 27 32 34 35 39 40 41 42 44 47 48 49 50 52 53 54 58 60 61 62 64 67 69 70 71 72 74 76 78 83 86 87 90 91 93 95 96 100 101 102 107 109 114 115 117 118 119 121 124 127 128 129 133 134 136 138 139 141 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 16...

result:

ok 9999 numbers

Test #9:

score: 10
Accepted
time: 715ms
memory: 198916kb

input:

2312255 279 3507885 55065619 99995923
5000 5000 50000
12411599 510042
9458515 510068
17180332 385087
255076 4340703
24970890 805109
24970891 80031
13829626 80081
660016 5373385
24224203 285090
425009 12372994
22150601 850070
24970897 635147
24970898 670164
12921645 70130
535155 24970900
24970901 505...

output:

1 5 6 7 8 9 11 12 15 16 19 21 24 25 26 27 30 31 32 34 35 36 39 40 41 46 47 49 54 58 59 60 63 68 69 70 71 72 74 79 83 84 86 92 94 95 98 101 110 112 113 114 116 118 119 120 121 122 123 125 128 130 131 132 133 135 139 140 141 142 143 144 145 147 149 150 151 153 156 157 158 160 161 164 165 168 169 171 1...

result:

ok 9999 numbers

Test #10:

score: 10
Accepted
time: 714ms
memory: 198936kb

input:

7012255 104 14758497 38070665 97795417
5000 5000 35000
740057 1488844
16425638 365098
10033259 310143
17813477 450085
400089 3137378
150011 18362827
445130 14285066
24978098 410072
185064 20009840
24978100 400099
19174287 515036
23242725 75087
11975709 405008
24978104 720067
680144 24978105
24978106...

output:

1 2 3 4 5 6 7 8 9 10 11 13 14 16 18 19 20 22 23 24 25 26 27 28 29 30 31 32 33 36 37 39 40 42 43 44 45 46 47 49 51 52 54 55 56 57 58 59 61 62 63 64 66 67 68 69 70 71 72 73 74 75 76 77 79 80 81 82 83 84 86 87 89 91 92 93 94 95 97 98 99 100 101 103 104 105 107 109 110 113 115 116 118 119 120 122 123 12...

result:

ok 9999 numbers

Extra Test:

score: 0
Extra Test Passed