QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #108765 | #67. Two Transportations | bashkort# | 0 | 12ms | 4264kb | C++20 | 3.9kb | 2023-05-26 17:06:38 | 2024-05-31 13:42:47 |
Judging History
Azer
#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
constexpr int maxN = 2000, maxQ = 58001;
constexpr int inf = 1e9 + 7;
int N, A, Q = 0, S = 0, usedCnt = 0;
vector<pair<int, int>> adj[maxN];
set<pair<int, int>> st;
int dist[maxN];
bool used[maxN], b[maxQ];
}
void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
std::vector<int> C) {
::N = N, ::A = A;
fill(dist, dist + N, inf);
dist[0] = 0;
used[0] = true;
for (int i = 0; i < A; ++i) {
adj[U[i]].emplace_back(V[i], C[i]);
adj[V[i]].emplace_back(U[i], C[i]);
}
for (auto [to, w] : adj[0]) {
if (dist[to] > dist[0] + w) {
st.erase({dist[to], to});
st.emplace(dist[to] = dist[0] + w, to);
}
}
for (int i = 0; i < 20; ++i) {
SendA(0);
}
}
void ReceiveA(bool x) {
b[Q++] = x;
if (Q % 20 == 0) {
int v = 0, d = 0, s = Q - 20;
for (int i = 0; i < 11; ++i) {
v |= b[s + i] << i;
}
for (int i = 0; i < 9; ++i) {
d |= b[s + 11 + i] << i;
}
// cout << "A received: " << v << "; dist0 = " << S + d << "; diff = " << d << endl;
if (v != 0) {
st.erase({dist[v], v});
st.emplace(dist[v] = min(dist[v], S + d), v);
}
if (st.empty()) {
return;
}
auto [dis, to] = *st.begin();
st.erase(st.begin());
assert(!used[to]);
used[to] = true;
for (auto [t, w] : adj[to]) {
if (!used[t] && dist[t] > dist[to] + w) {
st.erase({dist[t], t});
st.emplace(dist[t] = dist[to] + w, t);
}
}
int diff = dis - S;
S = dis;
for (int i = 0; i < 11; ++i) {
SendA(to >> i & 1);
}
for (int i = 0; i < 9; ++i) {
SendA(diff >> i & 1);
}
}
}
std::vector<int> Answer() {
std::vector<int> ans(N);
for (int k = 0; k < N; ++k) {
ans[k] = dist[k];
}
return ans;
}
Baijan
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
constexpr int maxN = 2000, maxQ = 58000;
constexpr int inf = 1e9 + 7;
int N, B, Q = 0, S = 0;
vector<pair<int, int>> adj[maxN];
set<pair<int, int>> st;
int dist[maxN];
bool used[maxN], b[maxQ];
}
void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
std::vector<int> D) {
::N = N, ::B = B;
fill(dist, dist + N, inf);
for (int i = 0; i < B; ++i) {
adj[S[i]].emplace_back(T[i], D[i]);
adj[T[i]].emplace_back(S[i], D[i]);
}
}
void ReceiveB(bool y) {
b[Q++] = y;
if (Q % 20 == 0) {
int v = 0, d = 0, s = Q - 20;
for (int i = 0; i < 11; ++i) {
v |= b[s + i] << i;
}
for (int i = 0; i < 9; ++i) {
d |= b[s + 11 + i] << i;
}
S += d;
used[v] = true;
st.erase({dist[v], v});
dist[v] = S + d;
// cout << "B received: " << v << "; dist0 = " << S << "; diff = " << d << endl;
for (auto [to, w] : adj[v]) {
if (!used[to] && dist[to] > dist[v] + w) {
st.erase({dist[to], to});
st.emplace(dist[to] = dist[v] + w, to);
}
}
if (st.empty()) {
for (int i = 0; i < 20; ++i) {
SendB(0);
}
} else {
auto [dis, to] = *st.begin();
assert(dis >= S);
assert(!used[to] && dis >= S);
for (int i = 0; i < 11; ++i) {
SendB(to >> i & 1);
}
for (int i = 0; i < 9; ++i) {
SendB((dis - S) >> i & 1);
}
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 4264kb
input:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 1 0 1 0 0 1 1 0 0 0 0 1 0 1 1 0 1 0 -1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 0 0 1 0 -1 1 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 -1 0 0 1 0 1 0 0 1 1 0 1 1 1 0 0 0 0 0 0 1 -1 0 1 0 0 0 1 1 0 0 0 0 1 1 0 1 1 0 1 0 0 -1 1 0 0 0 1 0 0 0 1 0 0 1 1 0 1 0 1 1 1 0 -1...
output:
-1 0 0 1 0 1 0 0 1 1 0 0 0 0 1 0 1 1 0 1 0 -1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 0 0 1 0 -1 1 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 -1 0 0 1 0 1 0 0 1 1 0 1 1 1 0 0 0 0 0 0 1 -1 0 1 0 0 0 1 1 0 0 0 0 1 1 0 1 1 0 1 0 0 -1 1 0 0 0 1 0 0 0 1 0 0 1 1 0 1 0 1 1 1 0 -1 0 1 1 0 0 1 0 1 0 0 1 1 0 1 0 0 0 1 0 0...
input:
output:
result:
wrong answer 1st lines differ - expected: '0', found: ''
Subtask #2:
score: 0
Wrong Answer
Test #7:
score: 8
Accepted
time: 1ms
memory: 3832kb
input:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 -1 -1
output:
-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 -1
input:
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Wrong Answer
time: 7ms
memory: 4240kb
input:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 1 1 0 -1 1 0 1 0 1 0 0 1 0 1 0 1 1 1 0 0 0 1 0 1 -1 0 0 1 1 0 0 1 1 0 1 0 1 1 1 0 1 0 1 0 0 -1 1 0 0 1 1 0 0 1 0 0 1 1 1 1 0 0 0 0 1 0 -1 1 0 1 0 0 1 0 0 1 0 1 1 1 0 1 0 1 1 0 0 -1 1 0 0 1 0 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 -1...
output:
-1 0 0 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 1 1 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 1 1 0 0 1 1 0 1 0 1 1 1 0 1 0 1 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 1 0 1 0 0 1 0 0 1 0 1 1 1 0 1 0 1 1 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 1 0 0 0 1 0 1 1 0 1 0 0 1 1 0 0 1 1 0...
input:
output:
result:
wrong answer 1st lines differ - expected: '0', found: ''
Subtask #3:
score: 0
Wrong Answer
Test #14:
score: 0
Wrong Answer
time: 12ms
memory: 3944kb
input:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 1 1 0 0 1 1 1 0 0 0 0 1 0 0 1 1 1 0 0 1 -1 1 1 1 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 -1 1 1 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 -1 1 0 1 0 1 1 1 1 1 1 0 1 0 1 1 1 0 0 0 0 -1 1 1 0 0 1 1 0 1 1 1 0 0 1 1 1 1 1 1 0 0 -1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 0 0 0 -1...
output:
-1 1 0 1 0 1 1 1 1 1 1 0 1 0 1 0 0 1 0 1 1 -1 1 0 1 0 1 1 1 1 1 1 0 0 0 1 1 0 1 1 0 0 -1 1 0 1 0 1 1 1 1 1 1 0 0 1 0 1 0 1 1 0 0 -1 1 0 1 0 1 1 1 1 1 1 0 1 0 1 1 1 0 0 0 0 -1 1 1 0 0 1 1 0 1 1 1 0 0 1 1 1 1 1 1 0 0 -1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 0 0 0 -1 1 1 0 1 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0...
input:
output:
result:
wrong answer 1st lines differ - expected: '0', found: ''
Subtask #4:
score: 0
Wrong Answer
Test #24:
score: 0
Wrong Answer
time: 6ms
memory: 3968kb
input:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 1 0 0 1 0 -1 0 1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 -1 0 1 1 1 0 1 0 1 0 0 0 1 0 1 0 1 1 0 0 0 -1 1 0 0 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 1 0 -1 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 0 -1 1 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 -1...
output:
-1 1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 1 0 0 1 0 -1 0 1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 -1 0 1 1 1 0 1 0 1 0 0 0 1 0 1 0 1 1 0 0 0 -1 1 0 0 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 1 0 -1 1 0 0 0 0 1 0 0 0 1 0 1 1 0 1 1 0 1 1 0 -1 1 0 0 0 0 1 0 0 0 1 0 1 1 1 0 1 1 1 0 0 -1 1 1 0 0 0 1 1 0 1 1 0 0 1 1 1 0 1 0 0 0...
input:
output:
0 2051 1928 1337 3109 3429 3267 2079 2797 3096 1785 1944 2313 1443 1581 1990 2562 2107 2637 1941 1402 2356 4051 2189 3995 2652 1794 3351 2398 3288 2580 2590 1426 1967 2497 1981 2673 2326 3763 1554 1964 2080 1775 2478 2217 2903 3387 3900 1243 1681 3189 2541 2843 3635 2553 2605 2044 725 2271 2825 1690...
result:
wrong answer 2nd lines differ - expected: '1881', found: '2051'
Subtask #5:
score: 0
Wrong Answer
Test #38:
score: 0
Wrong Answer
time: 1ms
memory: 4184kb
input:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 1 1 1 1 0 1 1 1 0 0 1 1 1 1 0 1 0 0 -1 1 0 0 0 0 1 1 0 1 1 0 1 1 0 1 0 0 1 1 1 -1 1 0 0 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 -1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 0 1 1 0 0 0 -1 1 0 1 0 1 0 0 1 0 0 0 1 0 0 1 1 1 1 1 0 -1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 1 0 -1...
output:
-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 1 0 0 0 0 1 1 0 1 1 0 1 1 0 1 0 0 1 1 1 -1 1 0 0 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 -1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 0 1 1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 1 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
input:
output:
0 3600 3223 3979 3707 4451 3374 4748 3979 2840 3728 3249 2820 3936 4920 4569 4574 3292 3860 4690 3639 3449 3325 2608 4225 3017 3859 4365 2896 3260 3338 2418 3518 3466 2966 2143 2299 4134 3772 3573 3293 3358 1664 5253 3114 3667 3389 3778 4564 3692 4243 3918 3991 3144 4149 3247 4438 3212 4196 4293 426...
result:
wrong answer 2nd lines differ - expected: '3467', found: '3600'
Subtask #6:
score: 0
Wrong Answer
Test #51:
score: 0
Wrong Answer
time: 1ms
memory: 3908kb
input:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 1 0 1 1 1 1 0 1 0 1 0 0 0 0 0 1 1 0 1 0 -1 0 1 1 1 0 1 0 1 1 1 0 0 1 0 1 1 1 1 1 1 -1 1 1 1 0 0 1 1 0 1 1 0 1 0 0 0 0 0 0 0 0 -1 0 1 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 -1 1 0 1 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 0 0 -1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 0 1 1 0 0 1 -1...
output:
-1 1 0 1 1 1 1 0 1 0 1 0 0 0 0 0 1 1 0 1 0 -1 0 1 1 1 0 1 0 1 1 1 0 0 1 0 1 1 1 1 1 1 -1 1 1 1 0 0 1 1 0 1 1 0 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 1 -1 1 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 0 0...
input:
output:
0 5072 3616 5453 4403 4106 4386 3892 4121 3685 5809 4765 4836 1864 3379 3818 5420 3273 4413 3913 3914 4493 4798 4975 3230 5075 3174 4027 5076 3281 4368 3397 3889 2436 4533 5138 4989 5245 5374 3986 4560 1948 3477 3943 4623 4063 3869 4215 5527 4714 3441 4526 4486 4392 4956 4405 4366 5328 3970 3542 300...
result:
wrong answer 2nd lines differ - expected: '4745', found: '5072'
Subtask #7:
score: 0
Wrong Answer
Test #64:
score: 0
Wrong Answer
time: 12ms
memory: 4076kb
input:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 1 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 1 1 -1 1 1 0 0 1 1 0 0 0 0 1 0 1 1 1 1 0 0 0 1 -1 1 1 0 1 1 0 1 0 0 1 0 1 0 0 0 1 0 0 0 1 -1 1 0 1 0 1 0 1 0 0 0 1 1 0 1 0 0 1 0 0 0 -1 0 1 0 0 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 -1 0 1 0 1 0 1 0 0 0 0 0 1 0 1 1 1 1 1 0 0 -1...
output:
-1 0 0 1 0 1 1 1 0 0 0 1 1 1 0 0 1 1 1 1 1 -1 1 1 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 1 -1 1 1 0 1 1 0 1 0 0 1 0 1 0 0 0 1 0 0 0 1 -1 1 0 1 0 1 0 1 0 0 0 1 1 0 1 0 0 1 0 0 0 -1 0 1 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0 1 1 1 -1 0 1 0 1 0 1 0 0 0 0 0 1 0 1 1 1 0 0 0 1 -1 0 1 0 0 1 1 1 0 1 1 1 0 1 1 0 0 1 1 0 0...
input:
output:
result:
wrong answer 1st lines differ - expected: '0', found: ''