QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #108785 | #67. Two Transportations | bashkort# | 0 | 49ms | 9140kb | C++20 | 4.6kb | 2023-05-26 17:26:18 | 2024-05-31 13:43:03 |
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 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);
}
}
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;
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;
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 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) {
// cerr << last << " " << Q - 1 << endl;
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;
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);
}
}
} 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;
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: 0ms
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: 3860kb
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: 8ms
memory: 3968kb
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: 15ms
memory: 4232kb
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 0 0 0 1 0 1 1 0 1 1 0 1 1 0 1 0 0 1 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 1 0 1 0 1 0 0 0 1 1 1 1 0 1 1 1 1 1 0 -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: 1ms
memory: 3816kb
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
output:
-1 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
input:
output:
0 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1...
result:
wrong answer 2nd lines differ - expected: '1881', found: '1000000007'
Subtask #5:
score: 0
Wrong Answer
Test #38:
score: 14
Accepted
time: 1ms
memory: 3924kb
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 0 -1 0 -1 1 0 0 0 0 1 1 1 0 1 1 0 1 1 0 0 0 1 0 1 1 -1 0 ...
input:
output:
0 3467 3039 3862 3565 4266 3258 4604 3860 2661 3573 3113 2706 3757 4805 4448 4392 3163 3673 4568 3500 3334 3197 2491 4036 2868 3743 4219 2747 3122 3210 2314 3397 3285 2805 2031 2187 3950 3654 3459 3114 3197 1499 5106 3000 3488 3210 3597 4420 3511 4094 3802 3848 2962 4031 3068 4292 3084 4077 4153 407...
result:
ok 1100 lines
Test #39:
score: 14
Accepted
time: 0ms
memory: 4156kb
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 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 -1 1 1 0 1 1 0 1 1 1 0 1 0 1 0 1 0 0 0 0 0 0 -1 1 1 1 1 1 0 1 1 1 1 0 0 0 1 1 0 0 0 0 0 0 -1 1 0 1 1 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 -1 1 0 1 1 0 1 0 0 1 1 0 0 0 1 1 ...
output:
-1 1 1 0 1 1 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 ...
input:
output:
0 485 399 2142 681 2834 3651 3030 983 464 2014 2770 2896 691 1552 1351 213 2098 1101 1045 3762 3341 778 644 3199 1965 2409 3611 1656 812 3557 329 613 1997 1194 2828 3289 1513 2336 3551 2512 317 1189 3282 880 3169 1565 3554 637 764 294 1573 3516 3593 756 1533 2643 1941 1944 3766 84 538 2659 3720 21 2...
result:
ok 1100 lines
Test #40:
score: 14
Accepted
time: 0ms
memory: 4164kb
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 0 0 0 1 0 0 1 1 0 0 0 1 1 1 1 -1 1 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 1 1 1 -1 1 1 1 0 0 1 1 0 1 0 1 0 0 1 1 0 0 1 1 1 1 -1 1 0 0 0 1 1 1 0 0 1 0 0 0 0 0 1 0 1 1 1 1 -1 1 0 1 0 1 1 0 0 0 0 1 0 0 1 1 1 0 1 1 1 1 -1 1 1 0 1 0 0 1 0 0 0 0 1 0 1 0 ...
output:
-1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 ...
input:
output:
0 210526 379348 30270 237071 524240 475727 459547 248812 335379 257106 398469 131103 219828 81790 511965 128693 170425 404799 477680 155716 337816 356356 346125 446801 82284 206625 383283 150289 57817 395524 346617 490398 326552 203201 92509 471818 114979 318729 122347 109099 175823 253216 192446 45...
result:
ok 1100 lines
Test #41:
score: 0
Wrong Answer
time: 49ms
memory: 9140kb
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 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 -1 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 -1 1 1 0 0 0 0 1 1 1 1 1 0 1 1 0 0 0 0 0 0 0 -1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 -1 1 0 0 0 0 1 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 -1 1 0 1 1 1 0 0 0 1 1 0 0 1...
output:
-1 1 1 0 0 0 1 1 0 0 1 0 0 0 1 0 1 0 0 0 0 0 -1 1 1 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 -1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 -1 1 0 1 0 1 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 -1 1 0 0 0 0 1 0 1 1 1 1 0 0 1 0 0 0 0 0 0 0 -1 1 0 1 1 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 -1 1 1 1 1 1 0 0 1 0 0 1 0 0 1...
input:
output:
0 2365 2592 4038 1606 415 3364 1277 5695 1848 3579 4252 5659 2845 3171 61 3703 765 1243 4359 1495 5118 3597 4419 5207 2621 3350 76 4962 503 4136 4231 2022 1159 2697 2981 5842 860 1555 5230 713 2960 4313 978 3237 986 5853 1881 350 4247 3957 2036 1666 4913 4143 2205 3494 3942 4443 4980 4783 3882 2722 ...
result:
wrong answer 2nd lines differ - expected: '2364', found: '2365'
Subtask #6:
score: 0
Wrong Answer
Test #51:
score: 0
Wrong Answer
time: 1ms
memory: 3976kb
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
output:
-1 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
input:
output:
0 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1000000007 1...
result:
wrong answer 2nd lines differ - expected: '4745', found: '1000000007'
Subtask #7:
score: 0
Wrong Answer
Test #64:
score: 0
Wrong Answer
time: 14ms
memory: 4072kb
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: ''