QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#719303 | #4740. Plan metra | nathan4690 | 11 | 11ms | 54068kb | C++17 | 2.3kb | 2024-11-07 00:07:50 | 2024-11-07 00:07:51 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define el cout << '\n'
#define f1(i,n) for(int i=1;i<=n;i++)
#define __file_name ""
using namespace std;
const ll maxn = 1e6+5, inf=1e18;
struct Edge{
int u, v, w;
Edge(){};
Edge(int u, int v, int w): u(u), v(v), w(w){};
};
int n,d[maxn], l[maxn];
vector<int> mp[2*maxn], allv;
vector<Edge> ans;
bool cmp(int x, int y){
return d[x] < d[y];
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
if(fopen(__file_name ".inp", "r")){
freopen(__file_name ".inp","r",stdin);
freopen(__file_name ".out","w",stdout);
}
// code here
cin >> n;
if(n == 2){
cout << "TAK\n1 2 1\n";
return 0;
}
for(int i=2;i<n;i++) cin >> d[i];
for(int i=2;i<n;i++) cin >> l[i];
for(int i=2;i<n;i++){
int diff = d[i] - l[i];
if(mp[diff + maxn].empty()) allv.push_back(diff);
mp[diff + maxn].push_back(i);
}
int duv = 1e9;
for(int i=2;i<n;i++) duv = min(duv, d[i] + l[i]);
if(abs(*allv.begin()) == abs(*allv.rbegin()) && allv.size() <= 2) duv = abs(*allv.begin());
if(mp[duv+maxn].empty()) allv.push_back(duv);
if(mp[-duv+maxn].empty()) allv.push_back(-duv);
mp[-duv+maxn].push_back(1); l[1] = duv;
mp[duv+maxn].push_back(n); d[n] = duv;
int rem2 = allv[0] & 1;
for(int item: allv) {
if((item & 1) != rem2) return cout << "NIE\n", 0;
sort(mp[item + maxn].begin(), mp[item + maxn].end(), cmp);
}
sort(allv.begin(), allv.end());
int pre = 1, dst = 0;
for(int item: allv){
int u = mp[item + maxn][0];
// cout << item << ' ' << u << ' ' << d[u] << ' ' << dst << endl;
// for(Edge e: ans){
// cout << e.u << ' ' << e.v << ' ' << e.w << '\n';
// }
if(u > 1){
if(dst >= d[u]) return cout << "NIE\n", 0;
ans.push_back(Edge(pre, u, d[u] - dst));
dst = d[u];
pre = u;
}
// int dst2 = dst;
for(int i=1;i<mp[item+maxn].size();i++){
int v = mp[item+maxn][i];
ans.push_back(Edge(u, v, d[v] - dst));
}
}
cout << "TAK\n";
for(Edge e: ans){
cout << e.u << ' ' << e.v << ' ' << e.w << '\n';
}
return 0;
}
詳細信息
Subtask #1:
score: 11
Accepted
Test #1:
score: 11
Accepted
time: 7ms
memory: 52604kb
input:
7 6 6 2 2 1 5 3 5 1 4
output:
TAK 1 6 1 1 4 2 1 5 2 5 2 4 5 7 1 7 3 3
result:
ok good solution
Test #2:
score: 11
Accepted
time: 3ms
memory: 50472kb
input:
10 31 89 20 19 19 20 19 164 70 88 20 20 20 19 20 125
output:
NIE
result:
ok no solution
Test #3:
score: 11
Accepted
time: 11ms
memory: 50480kb
input:
10 57 106 79 12 139 103 103 85 110 53 28 65 98 86 50 117
output:
NIE
result:
ok no solution
Test #4:
score: 11
Accepted
time: 9ms
memory: 50544kb
input:
10 13 62 24 125 13 15 54 94 1 76 14 113 1 1 68 82
output:
NIE
result:
ok no solution
Test #5:
score: 11
Accepted
time: 7ms
memory: 50532kb
input:
10 123 146 139 5 192 80 77 118 97 172 165 31 166 106 51 92
output:
TAK 1 5 5 1 7 80 1 4 139 1 3 146 1 10 26 10 8 51 10 9 92 10 2 97 10 6 166
result:
ok good solution
Test #6:
score: 11
Accepted
time: 0ms
memory: 54068kb
input:
10 112 67 152 16 6 28 1 8 111 82 137 31 21 41 14 7
output:
TAK 1 6 6 1 5 16 1 3 67 1 8 1 8 7 27 8 9 7 9 2 104 9 10 7 10 4 137
result:
ok good solution
Test #7:
score: 11
Accepted
time: 7ms
memory: 50536kb
input:
10 83 108 180 120 114 50 79 132 15 176 112 188 182 118 11 64
output:
TAK 1 7 50 1 3 108 1 6 114 1 5 120 1 10 68 10 8 11 10 2 15 10 9 64 10 4 112
result:
ok good solution
Test #8:
score: 11
Accepted
time: 0ms
memory: 50548kb
input:
10 65 149 150 119 51 90 64 172 66 150 151 120 52 91 65 173
output:
TAK 1 6 51 1 8 64 1 2 65 1 7 90 1 5 119 1 3 149 1 4 150 1 9 172 1 10 1
result:
ok good solution
Test #9:
score: 11
Accepted
time: 7ms
memory: 50592kb
input:
2
output:
TAK 1 2 1
result:
ok good solution
Test #10:
score: 11
Accepted
time: 7ms
memory: 50560kb
input:
10 46 145 46 19 165 20 145 99 47 146 47 112 76 112 146 6
output:
NIE
result:
ok no solution
Test #11:
score: 11
Accepted
time: 4ms
memory: 50536kb
input:
10 4 3 4 150 114 86 99 86 2 3 2 155 118 80 105 80
output:
NIE
result:
ok no solution
Test #12:
score: 11
Accepted
time: 3ms
memory: 50548kb
input:
10 6 7 12 168 171 12 7 7 6 5 14 180 159 14 6 5
output:
NIE
result:
ok no solution
Test #13:
score: 11
Accepted
time: 7ms
memory: 50600kb
input:
10 13 170 28 134 10 117 117 90 98 85 113 49 95 32 32 5
output:
TAK 1 6 10 1 2 13 1 4 28 1 10 85 10 9 5 10 7 32 10 8 32 10 5 49 10 3 85
result:
ok good solution
Test #14:
score: 11
Accepted
time: 7ms
memory: 50540kb
input:
10 90 2 53 53 158 58 1 114 89 1 54 54 161 59 2 111
output:
TAK 1 6 158 1 8 1 8 4 52 8 5 52 8 7 57 8 3 1 3 2 88 3 10 1 10 9 111
result:
ok good solution
Test #15:
score: 11
Accepted
time: 3ms
memory: 50540kb
input:
10 47 2 198 181 29 192 192 2 187 142 58 41 169 52 52 142
output:
TAK 1 3 2 1 9 2 1 6 29 1 2 47 1 10 140 10 5 41 10 7 52 10 8 52 10 4 58
result:
ok good solution
Test #16:
score: 11
Accepted
time: 3ms
memory: 50480kb
input:
10 78 128 140 162 140 110 191 70 79 129 141 163 141 111 192 71
output:
TAK 1 9 70 1 2 78 1 7 110 1 3 128 1 4 140 1 6 140 1 5 162 1 8 191 1 10 1
result:
ok good solution
Test #17:
score: 11
Accepted
time: 7ms
memory: 53684kb
input:
3 1 2
output:
TAK 1 2 1 1 3 1
result:
ok good solution
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #18:
score: 22
Accepted
time: 4ms
memory: 50548kb
input:
1000 998 997 996 995 994 993 992 991 990 989 988 987 986 985 984 983 982 981 980 979 978 977 976 975 974 973 972 971 970 969 968 967 966 965 964 963 962 961 960 959 958 957 956 955 954 953 952 951 950 949 948 947 946 945 944 943 942 941 940 939 938 937 936 935 934 933 932 931 930 929 928 927 926 925...
output:
TAK 1 999 1 999 998 1 998 997 1 997 996 1 996 995 1 995 994 1 994 993 1 993 992 1 992 991 1 991 990 1 990 989 1 989 988 1 988 987 1 987 986 1 986 985 1 985 984 1 984 983 1 983 982 1 982 981 1 981 980 1 980 979 1 979 978 1 978 977 1 977 976 1 976 975 1 975 974 1 974 973 1 973 972 1 972 971 1 971 970 ...
result:
ok good solution
Test #19:
score: 0
Wrong Answer
time: 4ms
memory: 50492kb
input:
1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...
output:
NIE
result:
wrong answer you didn't find a solution but jury did
Subtask #3:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%