QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #108789 | #67. Two Transportations | bashkort# | 0 | 9ms | 4196kb | C++20 | 4.5kb | 2023-05-26 17:29:40 | 2024-05-31 13:43:13 |
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, T = 0;
bool last = true;
vector<pair<int, int>> adj[maxN];
set<pair<int, int>> st;
int dist[maxN];
bool used[maxN], b[maxQ];
void upd(int v) {
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);
}
}
}
}
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]);
}
upd(0);
SendA(1);
for (int i = 0; i < 20; ++i) {
SendA(0);
}
}
void ReceiveA(bool x) {
b[Q++] = x;
T += last;
if (last && b[Q - 1] == 0 || !last && (Q - T) % 20 == 0) {
int v = -228, d = -228;
if (!last) {
v = 0, d = 0;
int 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;
}
if (v != 0) {
st.erase({dist[v], v});
st.emplace(dist[v] = min(dist[v], S + d), v);
}
}
last = true;
if (st.empty()) {
return;
}
auto [dis, to] = *st.begin();
st.erase(st.begin());
assert(!used[to]);
used[to] = true;
upd(to);
int diff = dis - S;
S = dis;
if (to == v && dis == d) {
SendA(0);
return;
} else {
SendA(1);
}
for (int i = 0; i < 11; ++i) {
SendA(to >> i & 1);
}
for (int i = 0; i < 9; ++i) {
SendA(diff >> i & 1);
}
} else {
last = false;
}
}
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, Sh = 0, T = 0;
bool last = true;
vector<pair<int, int>> adj[maxN];
set<pair<int, int>> st;
int dist[maxN];
bool used[maxN], b[maxQ];
void upd(int v) {
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);
}
}
}
}
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;
T += last;
if (last && b[Q - 1] == 0 || !last && (Q - T) % 20 == 0) {
if (!last) {
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;
// cerr << "B received: " << v << "; dist0 = " << S << "; diff = " << d << endl;
upd(v);
} else {
S = Sh;
}
last = true;
if (st.empty()) {
SendB(0);
} else {
SendB(1);
auto [dis, to] = *st.begin();
st.erase(st.begin());
assert(dis >= S);
assert(!used[to] && dis >= S);
Sh = dis;
upd(to);
for (int i = 0; i < 11; ++i) {
SendB(to >> i & 1);
}
for (int i = 0; i < 9; ++i) {
SendB((dis - S) >> i & 1);
}
}
} else {
last = false;
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 3980kb
input:
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 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 0 0 1 0 -1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 1 0 0 0 0 -1 1 0 0 1 0 1 0 0 1 1 0 1 1 1 0 0 0 0 0 0 1 -1 1 0 1 0 0 0 1 1 0 0 0 0 1 1 0 1 1 0 1 0 0 -1 1 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 -1 1 1 1 1 1 0 0 0 0 1 1 0 1...
output:
-1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 1 0 1 1 0 1 0 -1 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 0 0 1 0 -1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 1 0 0 0 0 -1 1 0 0 1 0 1 0 0 1 1 0 1 1 1 0 0 0 0 0 0 1 -1 1 0 1 0 0 0 1 1 0 0 0 0 1 1 0 1 1 0 1 0 0 -1 1 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 -1 1 1 1 1 1 0 0 0 0 1 1 0 1 1...
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: 3784kb
input:
1 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 -1 -1
input:
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Wrong Answer
time: 5ms
memory: 3984kb
input:
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 1 0 1 0 1 0 0 1 0 1 0 1 1 1 0 0 0 1 0 1 -1 1 0 0 1 1 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 1 -1 1 1 0 0 1 1 0 0 1 0 0 1 1 1 1 0 0 0 0 1 0 -1 1 1 0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 1 1 -1 1 1 0 0 1 0 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 -1 1 0 1 0 0 0 1 0 1 1 0 1 0...
output:
-1 1 0 0 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 1 1 0 -1 0 -1 1 0 0 1 1 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 1 -1 0 -1 1 1 0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 1 1 -1 0 -1 1 0 1 0 0 0 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 -1 0 -1 1 0 1 1 1 0 1 0 1 1 1 1 1 0 0 0 0 0 1 0 1 -1 0 -1 1 0 1 1 0 0 0 1 1 1 1 0 1 0 1 0 0 1 1 1 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: 9ms
memory: 4188kb
input:
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 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 1 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 -1 1 1 1 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 -1 1 1 0 1 0 1 1 1 1 1 1 0 1 0 1 1 1 0 0 0 0 -1 1 1 1 0 0 1 1 0 1 1 1 0 0 0 1 1 1 1 1 0 0 -1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 ...
output:
-1 1 1 0 1 0 1 1 1 1 1 1 0 1 0 1 0 0 1 0 1 1 -1 1 1 1 0 1 0 1 0 0 0 1 1 1 1 1 0 0 1 1 0 1 -1 1 1 1 0 0 1 1 0 1 1 1 0 0 1 1 0 0 1 1 1 0 -1 1 1 1 1 0 1 1 1 0 1 1 1 0 0 0 1 0 0 1 1 0 -1 1 1 0 0 0 1 0 1 1 0 1 1 0 1 0 1 0 1 0 0 1 -1 1 1 1 0 0 0 0 1 0 0 1 0 1 0 1 1 1 0 1 1 0 -1 1 1 0 0 0 0 0 0 0 1 1 0 1 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: 9ms
memory: 3912kb
input:
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 1 0 0 1 1 0 0 0 0 0 1 1 1 0 1 1 1 0 -1 1 0 1 1 1 0 1 0 1 0 0 0 1 0 1 0 1 1 0 0 0 -1 1 1 0 0 1 0 0 0 1 0 0 0 0 1 1 0 1 1 1 1 0 -1 1 1 0 0 1 1 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 -1 1 1 1 0 0 0 1 1 0 1 1 0 1 1 0 0 1 0 0 0 0 -1 1 1 0 0 0 0 1 0 0 0 1 0 0...
output:
-1 1 1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 1 0 0 1 0 -1 1 0 1 1 0 0 1 1 0 0 0 0 0 1 1 1 0 1 1 1 0 -1 1 0 1 1 1 0 1 0 1 0 0 0 1 0 1 0 1 1 0 0 0 -1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 1 0 0 0 0 1 -1 1 1 1 0 0 0 1 1 0 1 1 0 0 0 0 1 0 1 0 0 0 -1 1 1 0 0 0 0 1 0 0 0 1 0 1 1 1 1 0 0 1 0 0 -1 1 0 1 0 0 0 1 1 1 0 1 0 0 0...
input:
output:
0 1881 1737 1168 3083 3252 3240 1917 2249 2557 1616 1782 2120 1261 1381 1964 2536 2081 1957 1905 1175 2320 3849 1632 2795 2474 1769 2151 2218 2600 1895 2562 1266 1853 2468 1811 1989 1649 3075 1380 1928 2050 1753 2438 2193 1705 2694 2697 1096 1643 2498 2372 2816 2437 2515 2066 2019 705 2094 2798 1525...
result:
wrong answer 6th lines differ - expected: '3390', found: '3252'
Subtask #5:
score: 0
Wrong Answer
Test #38:
score: 0
Wrong Answer
time: 9ms
memory: 4176kb
input:
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 1 1 1 1 0 1 1 1 0 0 1 1 1 1 0 1 0 0 -1 1 1 0 0 0 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 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 1 0 0 0 0 1 1 1 1 1 0 0 0 1 0 1 1 0 0 0 -1 1 1 0 1 0 1 0 0 1 0 0 0 1 0 0 1 1 1 1 1 0 -1 1 0 0 1 0 1 1 0 0 1 1 0 0 0 1 ...
output:
-1 0 -1 1 1 0 0 0 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 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 1 0 0 0 0 1 1 1 1 1 0 0 0 1 0 1 1 0 0 0 -1 0 -1 1 0 1 1 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 1 1 -1 0 -1 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 1 1 1 0 1 -1 1 0 0 0 0 1 1 1 0 1 1 0 0 0 1 0 0 1 1 1 0 -1 0 -1 0 -1 0 ...
input:
output:
0 3467 3039 3862 3565 4266 3258 4398 3860 2661 3573 3113 2706 3757 4805 4448 3880 3163 3673 4056 3500 3334 3197 2491 3488 2868 3743 3707 2747 3122 3210 2314 3397 3285 2805 2031 2187 3950 3654 3459 3114 3197 1499 4900 3000 3488 3210 3597 4214 3511 4094 3802 3336 2962 4031 3068 4292 3084 3565 4153 356...
result:
wrong answer 8th lines differ - expected: '4604', found: '4398'
Subtask #6:
score: 0
Wrong Answer
Test #51:
score: 0
Wrong Answer
time: 7ms
memory: 4196kb
input:
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 1 1 0 1 0 1 1 1 0 0 1 0 1 0 0 1 0 1 -1 1 1 1 1 0 0 1 1 0 1 1 0 1 0 0 0 0 0 0 0 0 -1 1 0 1 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 -1 1 1 0 1 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 0 0 -1 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 0 1 1 0 0 1 -1 1 1 0 0 0 0 1 1 0 1 1 0 0...
output:
-1 1 1 0 1 1 1 1 0 1 0 1 0 0 0 0 0 1 1 0 1 0 -1 1 0 1 1 1 0 1 0 1 1 1 0 0 1 0 1 0 0 1 0 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 -1 1 1 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 1 0 1 -1 1 0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 1 0 0 1 0 -1 1 0 1 0 1 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 1 -1 1 1 0 0 1 0 1 0 1...
input:
output:
0 3721 1790 4621 3083 2273 3575 3057 3289 2627 3946 3926 3516 1609 1546 2469 4383 2430 3093 2593 2879 3148 3449 4134 1918 4038 2340 2715 4244 2484 2535 2588 3052 2168 3723 3825 4154 3896 4190 1639 3725 1181 1644 2620 3760 2720 3035 3381 4692 3875 2509 3476 3138 3556 4110 3225 3316 4146 2137 2711 220...
result:
wrong answer 2nd lines differ - expected: '4745', found: '3721'
Subtask #7:
score: 0
Wrong Answer
Test #64:
score: 0
Wrong Answer
time: 2ms
memory: 4080kb
input:
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 1 0 1 1 1 0 0 0 1 0 0 0 0 1 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 1 0 1 1 0 1 0 0 1 0 1 1 1 0 1 0 1 1 1 -1 1 1 0 1 0 1 0 1 0 0 0 1 0 1 1 0 0 1 1 0 0 -1 1 0 1 0 0 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 -1 1 0 1 0 1 0 1 0 0 0 0 0 1 0 1 ...
output:
-1 1 0 0 1 0 1 1 1 0 0 0 1 1 1 0 0 1 1 1 1 1 -1 1 1 1 0 0 1 1 0 0 0 0 1 1 1 0 0 1 1 1 1 1 -1 1 1 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 -1 1 1 0 1 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 -1 1 0 1 0 0 0 1 1 1 1 1 0 1 1 0 0 1 0 0 0 1 -1 1 0 1 0 1 0 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 -1 1 0 1 0 0 1 1 1 0 1 1 1 1 0...
input:
output:
result:
wrong answer 1st lines differ - expected: '0', found: ''