QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#376493 | #7680. Subway | arnold518 | WA | 2ms | 4028kb | C++17 | 2.0kb | 2024-04-04 10:47:06 | 2024-04-04 10:47:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 50;
const int P = 1e3;
const int Q = 1e9-1e4;
struct Data
{
int x, y, k, p;
};
int N, K;
Data A[MAXN+10];
int B;
int main()
{
scanf("%d", &N);
for(int i=1; i<=N; i++) scanf("%d%d%d", &A[i].x, &A[i].y, &A[i].k), K=max(K, A[i].k);
vector<int> V;
for(int i=1; i<=N; i++) for(int j=i+1; j<=N; j++)
{
int x1=A[i].x, y1=A[i].y, x2=A[i].x, y2=A[i].y;
if(x1==x2) continue;
if(((y2-y1)*(-3*P-x1))%(x2-x1)==0)
{
int y=(y2-y1)*(-3*P-x1)/(x2-x1)+y1;
if(-P<=y && y<=P) V.push_back(y);
}
}
sort(V.begin(), V.end());
for(int i=0; i<P; i++)
{
if(!binary_search(V.begin(), V.end(), i)) { B=i; break; }
if(!binary_search(V.begin(), V.end(), -i)) { B=-i; break; }
}
for(int j=1; j<=N; j++)
{
A[j].p=(ll)(A[j].y-B)*(Q-(-3*P))/(A[j].x-(-3*P))+B;
}
sort(A+1, A+N+1, [&](const Data &p, const Data &q) { return p.p<q.p; });
printf("%d\n", K);
for(int i=1; i<=K; i++)
{
int bef=-1;
vector<pii> V;
for(int j=1; j<=N; j++)
{
if(A[j].k>=i)
{
if(bef==-1)
{
V.push_back({Q, A[j].p-(K-i+1)});
V.push_back({A[j].x, A[j].y});
V.push_back({Q, A[j].p+(K-i)});
}
else
{
V.push_back({Q+i, bef});
V.push_back({Q+i, A[j].p-(K-i+1)});
V.push_back({Q, A[j].p-(K-i+1)});
V.push_back({A[j].x, A[j].y});
V.push_back({Q, A[j].p+(K-i)});
}
bef=A[j].p+(K-i);
}
}
printf("%d ", V.size());
for(auto [x, y] : V) printf("%d %d ", x, y);
printf("\n");
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3772kb
input:
3 1 2 1 2 1 2 3 3 2
output:
2 13 999990000 333106 2 1 999990000 333109 999990001 333109 999990001 666437 999990000 666437 1 2 999990000 666440 999990001 666440 999990001 998992 999990000 998992 3 3 999990000 998995 8 999990000 333107 2 1 999990000 333108 999990002 333108 999990002 998993 999990000 998993 3 3 999990000 998994
result:
ok ok Sum L = 21
Test #2:
score: 0
Accepted
time: 0ms
memory: 4024kb
input:
1 1 1 1
output:
1 3 999990000 333218 1 1 999990000 333219
result:
ok ok Sum L = 3
Test #3:
score: 0
Accepted
time: 1ms
memory: 3788kb
input:
1 1 1 50
output:
50 3 999990000 333169 1 1 999990000 333268 3 999990000 333170 1 1 999990000 333267 3 999990000 333171 1 1 999990000 333266 3 999990000 333172 1 1 999990000 333265 3 999990000 333173 1 1 999990000 333264 3 999990000 333174 1 1 999990000 333263 3 999990000 333175 1 1 999990000 333262 3 99999000...
result:
ok ok Sum L = 150
Test #4:
score: 0
Accepted
time: 1ms
memory: 3768kb
input:
50 662 -567 48 728 -120 7 307 669 27 -885 -775 21 100 242 9 -784 -537 41 940 198 46 736 -551 30 -449 456 16 -945 382 18 -182 810 49 213 187 44 853 245 48 617 -305 19 -81 261 3 617 208 8 -548 -652 6 -888 -667 14 -371 -812 43 202 -702 10 -668 -725 5 961 -919 33 -870 -697 50 428 810 29 560 405 7 348 -3...
output:
50 248 999990000 -366427745 -885 -775 999990000 -366427646 999990001 -366427646 999990001 -332959857 999990000 -332959857 -306 -897 999990000 -332959758 999990001 -332959758 999990001 -327227806 999990000 -327227806 -870 -697 999990000 -327227707 999990001 -327227707 999990001 -315812233 999990000 -...
result:
ok ok Sum L = 5865
Test #5:
score: 0
Accepted
time: 1ms
memory: 4024kb
input:
50 -772 697 1 -756 -909 1 659 923 1 850 471 1 260 -24 1 473 -639 1 -575 393 1 -466 197 1 333 -637 1 -192 -890 1 103 546 1 749 -723 1 -573 613 1 214 -138 1 277 928 1 266 291 1 911 275 1 -680 -67 1 69 190 1 -197 -795 1 684 618 1 729 -115 1 -658 -229 1 -595 -470 1 898 -172 1 401 81 1 133 685 1 223 400 ...
output:
1 248 999990000 -405077379 -756 -909 999990000 -405077378 999990001 -405077378 999990001 -337911659 999990000 -337911659 -162 -959 999990000 -337911658 999990001 -337911658 999990001 -316949349 999990000 -316949349 -192 -890 999990000 -316949348 999990001 -316949348 999990001 -294769448 999990000 -2...
result:
ok ok Sum L = 248
Test #6:
score: 0
Accepted
time: 1ms
memory: 3808kb
input:
50 -56 747 3 993 -490 4 930 -139 1 -298 -330 1 938 -351 5 -973 100 5 -472 44 4 345 628 5 481 -91 4 789 581 5 457 -29 4 871 -799 1 692 994 4 699 854 2 893 -33 1 -483 256 3 -962 -540 2 846 -893 1 830 609 5 845 -383 2 -552 -966 1 -544 -51 1 564 186 4 -615 -675 1 618 -911 3 -561 -302 4 -293 667 3 -334 -...
output:
5 248 999990000 -394605085 -552 -966 999990000 -394605076 999990001 -394605076 999990001 -338973510 999990000 -338973510 -637 -801 999990000 -338973501 999990001 -338973501 999990001 -293800093 999990000 -293800093 356 -986 999990000 -293800084 999990001 -293800084 999990001 -291216604 999990000 -29...
result:
ok ok Sum L = 695
Test #7:
score: 0
Accepted
time: 1ms
memory: 3736kb
input:
50 600 997 5 -893 -204 3 408 443 1 -560 -748 7 -647 161 6 -285 -980 1 87 -582 7 -48 -721 7 997 285 2 -189 -728 8 525 222 4 -324 816 9 760 317 3 753 -480 10 -813 -921 3 -325 -875 8 -747 816 10 -627 605 7 775 786 6 136 -54 2 274 948 10 216 -113 7 924 68 3 101 576 8 60 -501 2 898 801 8 -767 -974 10 -99...
output:
10 248 999990000 -436181461 -767 -974 999990000 -436181442 999990001 -436181442 999990001 -421121890 999990000 -421121890 -813 -921 999990000 -421121871 999990001 -421121871 999990001 -370671028 999990000 -370671028 -313 -996 999990000 -370671009 999990001 -370671009 999990001 -360955126 999990000 -...
result:
ok ok Sum L = 1385
Test #8:
score: -100
Wrong Answer
time: 2ms
memory: 4028kb
input:
50 24 -889 49 117 418 49 25 524 44 980 -416 43 -494 357 41 -287 -285 46 151 574 41 -289 68 49 -515 -540 41 -367 -178 47 -887 151 45 197 -272 47 714 724 45 -737 94 49 810 830 47 808 -695 41 537 -637 49 -142 -167 44 -749 -631 47 445 -444 42 801 910 43 59 363 42 -912 466 50 -649 -479 48 -958 -511 49 88...
output:
50 248 999990000 -337378115 -282 -917 999990000 -337378016 999990001 -337378016 999990001 -311542584 999990000 -311542584 75 -958 999990000 -311542485 999990001 -311542485 999990001 -293979473 999990000 -293979473 24 -889 999990000 -293979374 999990001 -293979374 999990001 -280317945 999990000 -2803...
result:
wrong answer Sum of L too large.