QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #719302 | #4740. Plan metra | nathan4690 | 0 | 8ms | 52904kb | C++17 | 2.3kb | 2024-11-07 00:07:21 | 2024-11-07 00:07:22 |
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 << "1 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: 0
Wrong Answer
Test #1:
score: 11
Accepted
time: 7ms
memory: 52904kb
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: 0ms
memory: 50500kb
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: 3ms
memory: 50532kb
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: 7ms
memory: 50464kb
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: 3ms
memory: 50440kb
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: 8ms
memory: 50516kb
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: 0ms
memory: 50500kb
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: 4ms
memory: 50524kb
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: 0
Wrong Answer
time: 3ms
memory: 50500kb
input:
2
output:
1 2 1
result:
wrong answer unknown token 1
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%