QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#183955 | #5669. Traveling in Jade City | MaGnsi0# | WA | 983ms | 42332kb | C++17 | 4.8kb | 2023-09-20 03:13:02 | 2023-09-20 03:13:02 |
Judging History
answer
/**
* author: MaGnsi0
* created: 19.09.2023 21:21:02
**/
#include <bits/stdc++.h>
using namespace std;
const int64_t OO = 1e12;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n; cin >> n;
int k; cin >> k; k--;
int m; cin >> m;
int Q; cin >> Q;
vector<int64_t> C(n);
for (int i = 0; i < n; ++i) {
cin >> C[i];
}
for (int i = 1; i < n; ++i) {
C[i] += C[i - 1];
}
vector<int64_t> X(m + 1);
for (int i = 0; i <= m; ++i) {
cin >> X[i];
}
for (int i = 1; i <= m; ++i) {
X[i] += X[i - 1];
}
set<int64_t> blockedC, blockedX;
blockedC.insert(-1), blockedC.insert(OO);
blockedX.insert(-1), blockedX.insert(OO);
function<int64_t(int, int)> go_clockwise = [&](int u, int v) {
if (u == v) { return int64_t(0); }
if (u < v) {
if (*blockedC.lower_bound(u) < v) {
return OO;
} else {
return int64_t(C[v - 1] - (u ? C[u - 1] : 0LL));
}
} else {
if (*blockedC.lower_bound(u) < n) {
return OO;
} else {
return C[n - 1] - (u ? C[u - 1] : 0) + go_clockwise(0, v);
}
}
assert(0);
return OO;
};
function<int64_t(int, int)> go_short = [&](int u, int v) {
if (u == v) { return int64_t(0); }
if (u > v) { swap(u, v); }
if (*blockedX.lower_bound(u) < v) {
return OO;
} else {
return int64_t(X[v - 1] - (u ? X[u - 1] : 0LL));
}
assert(0);
return OO;
};
while (Q--) {
char type;
cin >> type;
if (type == 'c') {
int c; cin >> c;
if (blockedC.count(c - 1)) {
blockedC.erase(c - 1);
} else {
blockedC.insert(c - 1);
}
} else if (type == 'x') {
int x; cin >> x;
if (blockedX.count(x)) {
blockedX.erase(x);
} else {
blockedX.insert(x);
}
} else {
int u; cin >> u; u--;
int v; cin >> v; v--;
if (0 <= u && u < n && 0 <= v && v < n) {
int64_t ans = OO;
ans = min(ans, go_clockwise(u, v));
ans = min(ans, go_clockwise(v, u));
ans = min(ans, go_clockwise(u, 0) + go_short(0, m + 1) + go_clockwise(k, v));
ans = min(ans, go_clockwise(u, k) + go_short(m + 1, 0) + go_clockwise(0, v));
ans = min(ans, go_clockwise(u, 0) + go_short(0, m + 1) + go_clockwise(v, k));
ans = min(ans, go_clockwise(u, k) + go_short(m + 1, 0) + go_clockwise(v, 0));
ans = min(ans, go_clockwise(0, u) + go_short(0, m + 1) + go_clockwise(k, v));
ans = min(ans, go_clockwise(k, u) + go_short(m + 1, 0) + go_clockwise(0, v));
ans = min(ans, go_clockwise(0, u) + go_short(0, m + 1) + go_clockwise(v, k));
ans = min(ans, go_clockwise(k, u) + go_short(m + 1, 0) + go_clockwise(v, 0));
ans = min(ans, go_clockwise(k, u) + go_short(m + 1, 0) + go_clockwise(v, 0));
if (ans == OO) {
cout << "impossible\n";
} else {
cout << ans << "\n";
}
} else if (u >= n && v >= n) {
int64_t ans = OO;
ans = min(ans, go_short(u - n + 1, v - n + 1));
ans = min(ans, go_short(u - n + 1, 0) + go_clockwise(0, k) + go_short(m + 1, v - n + 1));
ans = min(ans, go_short(v - n + 1, 0) + go_clockwise(0, k) + go_short(m + 1, u - n + 1));
ans = min(ans, go_short(u - n + 1, 0) + go_clockwise(k, 0) + go_short(m + 1, v - n + 1));
ans = min(ans, go_short(v - n + 1, 0) + go_clockwise(k, 0) + go_short(m + 1, u - n + 1));
if (ans == OO) {
cout << "impossible\n";
} else {
cout << ans << "\n";
}
} else {
if (v < n) { swap(u, v); }
int64_t ans = OO;
ans = min(ans, go_short(v - n + 1, 0) + go_clockwise(0, u));
ans = min(ans, go_short(v - n + 1, m + 1) + go_clockwise(0, u));
ans = min(ans, go_short(v - n + 1, 0) + go_clockwise(u, 0));
ans = min(ans, go_short(v - n + 1, m + 1) + go_clockwise(u, 0));
if (ans == OO) {
cout << "impossible\n";
} else {
cout << ans << "\n";
}
}
}
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
input:
4 3 1 9 2 3 8 4 1 1 q 3 4 x 0 q 3 4 c 3 q 3 4 c 1 q 3 4 x 0 q 3 4
output:
6 8 9 impossible 6
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
4 3 1 9 2 3 8 4 1 1 q 3 4 x 0 q 3 4 c 3 q 3 4 c 1 q 3 4 x 0 q 3 4
output:
6 8 9 impossible 6
result:
ok 5 lines
Test #3:
score: -100
Wrong Answer
time: 983ms
memory: 42332kb
input:
1000000 999999 1000000 1000000 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 2...
output:
177406400 122265000 70328000 impossible impossible impossible impossible impossible impossible impossible impossible impossible 29295200 impossible 22163200 impossible impossible impossible 11422200 impossible 62579800 impossible 35339400 impossible 20157200 impossible impossible impossible impossib...
result:
wrong answer 2nd lines differ - expected: '122264600', found: '122265000'