QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#86520#1898. Racetriplem5ds#AC ✓942ms153868kbC++202.3kb2023-03-10 00:07:252023-03-10 00:07:28

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-10 00:07:28]
  • 评测
  • 测评结果:AC
  • 用时:942ms
  • 内存:153868kb
  • [2023-03-10 00:07:25]
  • 提交

answer

///Enta etfsh5t nseet el rank

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
        tree_order_statistics_node_update>;
#define pb push_back
#define F first
#define S second
#define f(i, a, b) for (int i = a; i < b; i++)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(x) (int)(x).size()
//#define mp(x, y) make_pair(x, y)
#define popCnt(x) (__builtin_popcountll(x))
#define int ll

using ll = long long;
using ull = unsigned long long;
using uint = uint32_t;
using ii = pair<int, int>;

const int N = 3e6 + 6, A = 26, LG = 18, MOD = (119 << 23) + 1;
const long double PI = acos(-1);
const long double EPS = 1e-9;
const ll INF = 1e15;
int n, m;
int s[305], v[305], cnt[305][305];
map<ii, int> mp[305][305];

void doWork() {
    cin >> n;
    f(i, 1, n + 1) cin >> s[i] >> v[i];
    f(i, 1, n + 1)f(j, i + 1, n + 1)f(k, j + 1, n + 1) {
                int x1 = (s[j] - s[i]) * (k - j) - (s[k] - s[j]) * (j - i);
                int x2 = (v[k] - v[j]) * (j - i) - (v[j] - v[i]) * (k - j);
                if (x2 == 0 && x1 != 0)continue;
                if (x1 == 0 && x2 == 0)cnt[i][j] += 1;
                else {
                    int g = __gcd(x1, x2);
                    x1 /= g;
                    x2 /= g;
                    if (x2 < 0) {
                        x2 *= 1;
                        x1 *= -1;
                    }
                    if (x1 >= 0)
                        mp[i][j][{x1, x2}] += 1;
                }
            }
    int ans = 0;
    f(i, 1, n + 1)
        f(j, i + 1, n + 1) {
            int mx = 0;
            for (auto it: mp[i][j])mx = max(mx, it.S);
            ans = max(ans, mx + cnt[i][j]);
        }
    cout << ans + 2 << '\n';
}


int32_t main() {
#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif // ONLINE_JUDGE
    int t = 1;
//    cin >> t;
    while (t--)
        doWork();

    return 0;
}


这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 7952kb

input:

3
0 1
0 3
3 2

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 5ms
memory: 7956kb

input:

10
6648 37
13620 78
11242 64
28 43
99 86
-78 59
16180 93
17372 100
73 76
-83 43

output:

3

result:

ok 1 number(s): "3"

Test #3:

score: 0
Accepted
time: 1ms
memory: 7888kb

input:

10
-32705 188
-32879 189
-7153 42
-44777 257
-35326 203
-42500 244
-59 170
-34448 198
-31997 184
-13971 81

output:

9

result:

ok 1 number(s): "9"

Test #4:

score: 0
Accepted
time: 2ms
memory: 7888kb

input:

10
-4225 87
-8905 221
-3925 79
-185 4
-6075 141
-2495 39
-1470 10
-1740 18
-5685 131
-6270 148

output:

9

result:

ok 1 number(s): "9"

Test #5:

score: 0
Accepted
time: 1ms
memory: 7764kb

input:

10
-24855 193
-16590 134
-32220 252
-330 18
-18390 154
-29025 235
-16710 146
-5205 63
-28935 241
241 236

output:

9

result:

ok 1 number(s): "9"

Test #6:

score: 0
Accepted
time: 1ms
memory: 7804kb

input:

10
-35544 180
107 154
-27781 141
-279 207
-42 179
-295 279
-21608 110
-26781 136
-29964 152
-55 92

output:

5

result:

ok 1 number(s): "5"

Test #7:

score: 0
Accepted
time: 2ms
memory: 7936kb

input:

10
-125 147
-12890 260
-5387 133
200 180
-12388 252
240 82
-13666 274
-5691 139
-187 42
294 196

output:

5

result:

ok 1 number(s): "5"

Test #8:

score: 0
Accepted
time: 0ms
memory: 7768kb

input:

10
-293 272
-100830 285
-78410 145
-56464 8
297 28
-83514 183
-297 283
93 16
-56702 19
177 199

output:

5

result:

ok 1 number(s): "5"

Test #9:

score: 0
Accepted
time: 2ms
memory: 7956kb

input:

10
-287 7
-31 159
141 265
-209 193
6 38
-191 63
-22 215
-12509 55
-140 98
139 161

output:

3

result:

ok 1 number(s): "3"

Test #10:

score: 0
Accepted
time: 2ms
memory: 7764kb

input:

10
-96 212
-16 135
-202 218
79 224
-296 137
194 294
-253 122
-138 129
-46933 297
-266 114

output:

3

result:

ok 1 number(s): "3"

Test #11:

score: 0
Accepted
time: 2ms
memory: 7968kb

input:

10
174 144
-163 265
132 165
-21951 279
-75 65
-72 247
190 104
178 3
-270 115
142 73

output:

3

result:

ok 1 number(s): "3"

Test #12:

score: 0
Accepted
time: 365ms
memory: 56680kb

input:

239
-86 11
508 13
2850 91
2642 84
96 88
3126 100
2618 83
1510 46
2352 74
1004 29
1486 45
-14 46
4 11
2422 76
2154 67
-96 76
-77 97
55 72
3002 95
2104 65
99 2
2198 68
2680 84
-63 34
75 40
1006 28
1308 38
-85 45
34 47
88 46
-22 59
1 99
64 5
66 27
1564 46
2916 91
2078 63
-20 92
44 23
1904 57
15 80
2118...

output:

5

result:

ok 1 number(s): "5"

Test #13:

score: 0
Accepted
time: 190ms
memory: 34660kb

input:

239
-8077 281
-7824 272
-4099 139
-3734 126
-7261 252
-2388 78
-4375 149
-71 57
40 81
-4624 158
-4063 138
-5518 190
-3697 125
-1400 43
-1315 40
-1258 38
104 52
-892 25
-2963 99
-3522 119
-833 23
-23 196
-7635 266
-3210 108
-1893 61
-268 3
-295 4
-854 24
-4269 146
-768 21
-5415 187
-5386 186
-2221 73...

output:

216

result:

ok 1 number(s): "216"

Test #14:

score: 0
Accepted
time: 202ms
memory: 34220kb

input:

239
-19532 242
-9414 109
-23540 295
-20642 257
130 177
-21382 267
-10124 119
-13078 158
-4632 47
-23774 299
-14416 176
-4906 51
-10444 124
-10358 123
-17492 217
-17862 222
-22032 277
-10850 130
-19428 243
141 37
-10440 125
-22970 290
-8748 103
-7370 85
-2952 27
-17762 222
-15700 195
-13030 160
-1332...

output:

216

result:

ok 1 number(s): "216"

Test #15:

score: 0
Accepted
time: 201ms
memory: 32520kb

input:

239
27010 134
27780 132
53460 24
28615 131
42310 74
17230 182
45260 64
25585 149
60665 1
50390 46
15675 195
59685 9
29670 138
17750 190
-6390 294
34800 120
12540 216
-85 271
-51 156
19785 189
58860 24
-3350 290
2590 266
-113 257
63115 11
670 278
127 257
30645 153
51155 67
44640 96
-650 290
67330 2
6...

output:

216

result:

ok 1 number(s): "216"

Test #16:

score: 0
Accepted
time: 472ms
memory: 77812kb

input:

239
-55416 264
184 153
-186 259
20 16
219 276
85 188
179 200
-269 233
-12997 63
-58783 280
-56883 271
-20379 98
2 278
6 280
118 139
-48016 229
-4127 21
-6025 30
-29234 140
154 84
-113 242
-58349 278
13 248
-21633 104
177 170
-140 122
-102 22
-56655 270
28 147
227 136
-20993 101
48 300
73 46
-47365 2...

output:

119

result:

ok 1 number(s): "119"

Test #17:

score: 0
Accepted
time: 441ms
memory: 81836kb

input:

239
20 2
-1970 12
27 251
-176 240
195 218
-1130 8
142 14
-31510 160
-51300 259
151 79
-151 129
-29270 149
-59 176
-77 299
-41840 212
-231 298
104 178
-290 251
-44600 226
-27390 140
155 224
-67 18
-56960 288
184 96
53 135
-146 93
-1920 13
-240 52
-15700 82
185 215
66 178
-28270 145
-170 244
91 44
-17...

output:

119

result:

ok 1 number(s): "119"

Test #18:

score: 0
Accepted
time: 490ms
memory: 91000kb

input:

239
102 116
-150 291
-230 81
-41431 109
77 64
-38241 99
-18257 23
-258 218
101 298
279 131
-77663 257
-237 281
-80171 269
-41 232
-18965 35
-2 127
-17329 31
-70383 237
-23204 56
-80143 277
-46691 149
-57528 192
-60595 205
-208 287
-49894 166
-72127 253
103 267
-54951 189
203 99
-230 21
202 123
29 25...

output:

119

result:

ok 1 number(s): "119"

Test #19:

score: 0
Accepted
time: 477ms
memory: 76872kb

input:

239
152 73
-120 174
290 185
-251 155
-140 279
-37 165
10 202
-188 284
29 141
-35561 228
-198 268
-90 100
-14013 89
-235 156
69 26
-30750 197
-208 208
-19 57
-82 282
-9 295
-15 202
-144 195
-29813 191
43 23
-167 288
-267 154
-78 185
-137 60
-60 292
-209 52
71 279
179 279
71 206
-146 117
-73 99
-183 3...

output:

23

result:

ok 1 number(s): "23"

Test #20:

score: 0
Accepted
time: 474ms
memory: 78640kb

input:

239
-121 78
32 252
-104 51
107 287
152 55
213 157
5 243
-194 60
49 247
36 149
-238 179
-138 168
-75 76
-65 117
-91 197
249 285
-272 120
-136 29
-107 29
-287 165
-8298 31
-216 83
-258 217
242 53
139 117
-176 25
224 77
188 224
108 54
-83 260
53 226
-29 78
-207 215
-295 203
-231 272
158 223
-108 149
21...

output:

23

result:

ok 1 number(s): "23"

Test #21:

score: 0
Accepted
time: 441ms
memory: 77412kb

input:

239
64 78
-78 139
-48726 169
242 259
105 118
19 36
-214 141
43 50
173 294
151 17
-49 104
271 4
254 14
37 19
41 182
94 149
61 174
268 285
-161 203
-98 20
127 136
-33 239
-117 120
-175 283
295 97
157 259
-299 258
-214 3
-255 104
-28 147
142 46
18 263
-140 291
33 144
101 247
20 27
-245 142
-275 132
62 ...

output:

23

result:

ok 1 number(s): "23"

Test #22:

score: 0
Accepted
time: 756ms
memory: 115240kb

input:

300
66 72
3811 43
3813 43
509 5
80 33
8430 96
4604 52
1561 17
2868 32
-22 90
-27 64
81 16
-50 11
11 25
-63 93
96 12
7930 90
5496 62
4193 47
367 3
4458 50
-46 48
-23 54
8031 91
3161 35
-21 83
5 54
-52 32
-16 20
735 7
-91 97
-97 36
-10 94
4136 46
0 10
-43 64
6404 72
-83 76
8322 94
-46 23
4846 54
7632 ...

output:

7

result:

ok 1 number(s): "7"

Test #23:

score: 0
Accepted
time: 363ms
memory: 59124kb

input:

300
-13477 69
-45261 232
-9965 51
-1579 8
-33753 173
-35312 181
-32386 166
-55005 282
-47594 244
15 21
-57732 296
-24776 127
-27895 143
-13854 71
-31013 159
-52072 267
-4686 24
-41540 213
-24184 124
-52068 267
-44852 230
-35686 183
-54990 282
-7214 37
-50893 261
-35487 182
-53036 272
-17740 91
-2144...

output:

270

result:

ok 1 number(s): "270"

Test #24:

score: 0
Accepted
time: 357ms
memory: 55500kb

input:

300
-13515 127
-25055 237
-3310 30
-26715 253
-28175 267
-16300 154
-3480 32
-4415 41
-19735 187
-3765 35
-12470 118
-3220 30
-187 238
-25040 238
-13375 127
-23235 221
-15245 145
-1165 11
-26040 248
-3980 38
-11 283
207 98
-16970 162
-6040 58
-10335 99
-26390 252
-24700 236
-2955 29
-27095 259
-1333...

output:

270

result:

ok 1 number(s): "270"

Test #25:

score: 0
Accepted
time: 345ms
memory: 47520kb

input:

300
34132 244
65164 88
74329 43
65567 89
68625 75
35632 244
62724 108
28352 284
33577 259
66776 92
82048 16
78014 38
-216 173
74477 59
62366 122
58332 144
80499 33
-78 20
40714 238
72140 80
63378 126
38659 253
88406 2
77674 58
35422 274
57983 161
55919 173
50309 203
75037 79
36331 277
64211 137
6037...

output:

270

result:

ok 1 number(s): "270"

Test #26:

score: 0
Accepted
time: 860ms
memory: 141620kb

input:

300
-23449 256
30 271
74 61
-15074 164
-15710 171
-2 66
-11795 128
-1966 20
219 281
57 10
-152 273
-12609 137
192 51
-18431 201
-66 244
-24526 268
-261 205
73 200
-72 251
-25705 281
-2590 27
70 29
173 173
38 237
-3132 33
51 41
-35 266
124 254
-22784 249
-12864 140
-1306 13
-105 203
231 189
-119 246
...

output:

150

result:

ok 1 number(s): "150"

Test #27:

score: 0
Accepted
time: 942ms
memory: 153868kb

input:

300
-16834 78
-38337 179
-48977 229
-40447 189
-53430 250
-239 250
175 233
-14208 66
47 55
-25051 117
-17799 83
-31208 146
197 82
250 7
-34799 163
-36067 169
-135 131
-16451 77
-159 186
-40074 188
-12800 60
-4057 19
-96 220
-200 169
-212 201
137 34
-58109 273
-15073 71
-45096 212
-268 106
-26332 124...

output:

150

result:

ok 1 number(s): "150"

Test #28:

score: 0
Accepted
time: 907ms
memory: 138512kb

input:

300
62502 59
55032 94
204 130
-27 124
-272 172
-65 79
81 107
62 241
76446 7
253 144
40416 172
96 230
67212 54
66846 57
47166 147
42360 170
147 106
137 55
71232 44
-271 7
59622 99
-35 88
181 279
65184 78
59490 105
81 259
18798 291
69048 66
-239 243
19254 293
-148 299
252 155
8 274
28668 256
58938 121...

output:

150

result:

ok 1 number(s): "150"

Test #29:

score: 0
Accepted
time: 917ms
memory: 142800kb

input:

300
-253 282
-93 221
41 262
-146 181
290 256
190 245
-17534 276
55 80
102 57
19 101
212 84
92 175
-146 59
-223 84
-160 257
62 149
-1 243
122 293
129 197
-11889 188
-177 131
-294 62
51 235
165 66
82 242
-286 22
109 286
2 8
-166 159
36 237
146 233
-287 167
-163 4
-230 221
-82 17
-261 188
171 217
137 4...

output:

30

result:

ok 1 number(s): "30"

Test #30:

score: 0
Accepted
time: 917ms
memory: 142680kb

input:

300
-125 3
-286 41
-209 62
-152 124
290 294
-66638 277
-68 88
-264 172
-222 122
-79 120
-63172 263
-134 143
246 41
-21174 91
-34340 145
158 261
-204 14
-297 126
40 125
129 16
220 244
294 268
-8884 41
-285 157
-179 188
-198 132
-148 19
-300 245
110 58
113 207
-117 121
-237 152
81 288
237 189
190 145
...

output:

30

result:

ok 1 number(s): "30"

Test #31:

score: 0
Accepted
time: 931ms
memory: 144236kb

input:

300
180 142
97 196
132 212
-224 245
-187 33
-226 14
154 43
-57 46
-255 26
155 248
-69 157
63 3
83 242
32644 182
-179 116
-171 191
-124 123
235 100
-79 7
137 231
-123 131
-270 149
86 13
105 96
43 103
-62 82
21 26
-216 254
-156 210
242 88
-95 60
32766 273
268 59
114 148
31 144
127 11
138 127
179 83
19...

output:

30

result:

ok 1 number(s): "30"