QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#377244 | #7680. Subway | arnold518 | WA | 1ms | 4060kb | C++17 | 2.8kb | 2024-04-05 06:54:00 | 2024-04-05 06:54:00 |
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-4e3;
struct Data
{
int x, y, k, p;
};
int N, K;
vector<Data> A1, A2;
int B1, B2;
int main()
{
scanf("%d", &N);
for(int i=1; i<=N; i++)
{
Data p;
scanf("%d%d%d", &p.x, &p.y, &p.k);
if(p.x>0) A1.push_back(p);
else A2.push_back(p);
K=max(K, p.k);
}
vector<int> V1, V2;
for(int i=0; i<A1.size(); i++) for(int j=i+1; j<A1.size(); j++)
{
int x1=A1[i].x, y1=A1[i].y, x2=A1[i].x, y2=A1[i].y;
if(x1==x2) continue;
if(((y2-y1)*(-P-x1))%(x2-x1)==0)
{
int y=(y2-y1)*(-P-x1)/(x2-x1)+y1;
if(-P<=y && y<=P) V1.push_back(y);
}
}
sort(V1.begin(), V1.end());
for(int i=0; i<=P; i++)
{
if(!binary_search(V1.begin(), V1.end(), i)) { B1=i; break; }
if(!binary_search(V1.begin(), V1.end(), -i)) { B1=-i; break; }
}
for(int i=0; i<A1.size(); i++) A1[i].p=(ll)(A1[i].y-B1)*(Q-(-P))/(A1[i].x-(-P))+B1;
for(int i=0; i<A2.size(); i++) for(int j=i+1; j<A2.size(); j++)
{
int x1=A2[i].x, y1=A2[i].y, x2=A2[j].x, y2=A2[j].y;
if(x1==x2) continue;
if(((y2-y1)*(P-x1))%(x2-x1)==0)
{
int y=(y2-y1)*(P-x1)/(x2-x1)+y1;
if(-P<=y && y<=P) V2.push_back(y);
}
}
sort(V2.begin(), V2.end());
for(int i=0; i<=P; i++)
{
if(!binary_search(V2.begin(), V1.end(), i)) { B2=i; break; }
if(!binary_search(V2.begin(), V1.end(), -i)) { B2=-i; break; }
}
for(int i=0; i<A2.size(); i++) A2[i].p=(ll)(A2[i].y-B2)*(-Q-P)/(A2[i].x-P)+B2;
sort(A1.begin(), A1.end(), [&](const Data &p, const Data &q) { return p.p<q.p; });
sort(A2.begin(), A2.end(), [&](const Data &p, const Data &q) { return p.p>q.p; });
printf("%d\n", K);
for(int i=1; i<=K; i++)
{
vector<pii> V;
for(int j=0; j<A1.size(); j++)
{
if(A1[j].k>=i)
{
V.push_back({Q+i, A1[j].p-(K-i+1)});
V.push_back({A1[j].x, A1[j].y});
V.push_back({Q+i, A1[j].p+(K-i)});
}
}
V.push_back({Q+i, 1e9-K+i});
V.push_back({-Q-i, 1e9-K+i});
for(int j=0; j<A2.size(); j++)
{
if(A2[j].k>=i)
{
V.push_back({-Q-i, A2[j].p+(K-i)});
V.push_back({A2[j].x, A2[j].y});
V.push_back({-Q-i, A2[j].p-(K-i+1)});
}
}
printf("%d ", V.size());
for(auto [x, y] : V) printf("%d %d ", x, y);
printf("\n");
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 4060kb
input:
3 1 2 1 2 1 2 3 3 2
output:
2 11 999996001 997998 2 1 999996001 998001 999996001 1997994 1 2 999996001 1997997 999996001 2991015 3 3 999996001 2991018 999996001 999999999 -999996001 999999999 8 999996002 997999 2 1 999996002 998000 999996002 2991016 3 3 999996002 2991017 999996002 1000000000 -999996002 1000000000
result:
ok ok Sum L = 19
Test #2:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
1 1 1 1
output:
1 5 999996001 998997 1 1 999996001 998998 999996001 1000000000 -999996001 1000000000
result:
ok ok Sum L = 5
Test #3:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
1 1 1 50
output:
50 5 999996001 998948 1 1 999996001 999047 999996001 999999951 -999996001 999999951 5 999996002 998949 1 1 999996002 999046 999996002 999999952 -999996002 999999952 5 999996003 998950 1 1 999996003 999045 999996003 999999953 -999996003 999999953 5 999996004 998951 1 1 999996004 999044 999996004 9...
result:
ok ok Sum L = 250
Test #4:
score: 0
Accepted
time: 1ms
memory: 3736kb
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 152 999996001 -669413334 334 -893 999996001 -669413235 999996001 -584024920 202 -702 999996001 -584024821 999996001 -468637093 961 -919 999996001 -468636994 999996001 -341154261 662 -567 999996001 -341154162 999996001 -317395411 736 -551 999996001 -317395312 999996001 -238871736 348 -322 99999600...
result:
ok ok Sum L = 3679
Test #5:
score: 0
Accepted
time: 0ms
memory: 3804kb
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 152 999996001 -843686790 30 -869 999996001 -843686789 999996001 -477868034 333 -637 999996001 -477868033 999996001 -463233905 360 -630 999996001 -463233904 999996001 -433807253 473 -639 999996001 -433807252 999996001 -413377834 749 -723 999996001 -413377833 999996001 -210761700 115 -235 999996001 ...
result:
ok ok Sum L = 152
Test #6:
score: -100
Wrong Answer
time: 0ms
memory: 4056kb
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 152 999996001 -744343887 17 -757 999996001 -744343878 999996001 -727136466 356 -986 999996001 -727136457 999996001 -723291603 348 -975 999996001 -723291594 999996001 -563039106 618 -911 999996001 -563039097 999996001 -531366039 594 -847 999996001 -531366030 999996001 -483747199 846 -893 999996001 ...
result:
wrong answer Integer parameter [name=y_i] equals to 1650356521, violates the range [-10^9, 10^9]