QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#86520 | #1898. Race | triplem5ds# | AC ✓ | 942ms | 153868kb | C++20 | 2.3kb | 2023-03-10 00:07:25 | 2023-03-10 00:07:28 |
Judging History
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"