QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #121159 | #67. Two Transportations | zhylj | 0 | 95ms | 19104kb | C++20 | 4.5kb | 2023-07-07 17:29:14 | 2023-07-07 17:29:16 |
Judging History
Azer
#include "Azer.h"
#include <bits/stdc++.h>
namespace {
#define fi first
#define se second
#define mkp std::make_pair
typedef unsigned ui;
typedef long long ll;
typedef unsigned long long ull;
typedef double ff;
typedef std::pair <int, int> pii;
const int N_MAX = 2000 + 5, INF = 0x3fffffff, CINF = 511;
int N, d[N_MAX], lst_mn, cur_mn_idx, cur_mn, cnt, cnt_mx, res;
bool flag[N_MAX];
std::vector <int> q;
std::vector <pii> E[N_MAX];
void Add(int u, int v, int w) {
E[u].push_back(mkp(v, w));
E[v].push_back(mkp(u, w));
}
} // namespace
void InitA(int N, int A, std::vector <int> U, std::vector <int> V,
std::vector <int> C) {
memset(flag, false, sizeof(flag));
::N = res = N;
for(int i = 0; i < A; ++i)
Add(U[i], V[i], C[i]);
for(int i = 0; i < N; ++i)
d[i] = INF;
d[0] = lst_mn = 0; flag[0] = true;
for(auto p : E[0]) {
int v = p.fi, w = p.se;
d[v] = std::min(d[v], d[0] + w);
}
cur_mn = CINF;
for(int i = 0; i < N; ++i)
if(!flag[i] && cur_mn > d[i] - lst_mn) {
cur_mn = d[i] - lst_mn;
cur_mn_idx = i;
}
for(int i = 0; i < 9; ++i)
SendA((cur_mn >> i) & 1);
cnt_mx = 9; q.clear();
--res;
}
void ReceiveA(bool x) {
++cnt; q.push_back((int)x);
if(cnt < cnt_mx) return;
int val = 0;
for(int i = 0; i < cnt_mx; ++i)
if(q[i]) val |= 1 << i;
q.clear(); cnt = 0;
std::cerr << "Receive A: " << cnt_mx << " " << val << std::endl;
if(cnt_mx == 9) {
--res;
if(cur_mn < val) { // if B, then '<='
int u = cur_mn_idx;
std::cerr << "SendA 11 bits: " << u << std::endl;
for(int i = 0; i < 11; ++i)
SendA((u >> i) & 1);
if(res) cnt_mx = 9;
else cnt_mx = 0;
} else {
cur_mn = val;
cnt_mx = 11;
return;
}
} else if(cnt_mx == 11) {
cur_mn_idx = val;
if(res) cnt_mx = 9;
else cnt_mx = 0;
}
lst_mn += cur_mn;
int u = cur_mn_idx;
flag[u] = true;
d[u] = lst_mn;
for(auto p : E[u]) {
int v = p.fi, w = p.se;
d[v] = std::min(d[v], d[u] + w);
}
cur_mn = CINF;
for(int i = 0; i < N; ++i)
if(!flag[i] && cur_mn > d[i] - lst_mn) {
cur_mn = d[i] - lst_mn;
cur_mn_idx = i;
}
if(cur_mn != CINF) {
for(int i = 0; i < 9; ++i)
SendA((cur_mn >> i) & 1);
}
}
std::vector<int> Answer() {
std::vector<int> ans(N);
for(int k = 0; k < N; ++k)
ans[k] = d[k];
return ans;
}
Baijan
#include "Baijan.h"
#include <bits/stdc++.h>
namespace {
#define fi first
#define se second
#define mkp std::make_pair
typedef unsigned ui;
typedef long long ll;
typedef unsigned long long ull;
typedef double ff;
typedef std::pair <int, int> pii;
const int N_MAX = 2000 + 5, INF = 0x3fffffff, CINF = 511;
int N, d[N_MAX], lst_mn, cur_mn_idx, cur_mn, cnt, cnt_mx, res;
bool flag[N_MAX];
std::vector <int> q;
std::vector <pii> E[N_MAX];
void Add(int u, int v, int w) {
E[u].push_back(mkp(v, w));
E[v].push_back(mkp(u, w));
}
} // namespace
void InitB(int N, int A, std::vector <int> U, std::vector <int> V,
std::vector <int> C) {
memset(flag, false, sizeof(flag));
::N = res = N;
for(int i = 0; i < A; ++i)
Add(U[i], V[i], C[i]);
for(int i = 0; i < N; ++i)
d[i] = INF;
d[0] = lst_mn = 0; flag[0] = true;
for(auto p : E[0]) {
int v = p.fi, w = p.se;
d[v] = std::min(d[v], d[0] + w);
}
cur_mn = CINF;
for(int i = 0; i < N; ++i)
if(!flag[i] && cur_mn > d[i] - lst_mn) {
cur_mn = d[i] - lst_mn;
cur_mn_idx = i;
}
for(int i = 0; i < 9; ++i)
SendB((cur_mn >> i) & 1);
cnt_mx = 9; q.clear();
--res;
}
void ReceiveB(bool x) {
++cnt; q.push_back((int)x);
if(cnt < cnt_mx) return;
int val = 0;
for(int i = 0; i < cnt_mx; ++i)
if(q[i]) val |= 1 << i;
q.clear(); cnt = 0;
std::cerr << "Receive B: " << cnt_mx << " " << val << std::endl;
if(cnt_mx == 9) {
--res;
if(cur_mn <= val) { // if B, then '<='
int u = cur_mn_idx;
std::cerr << "SendB 11 bits" << std::endl;
for(int i = 0; i < 11; ++i)
SendB((u >> i) & 1);
if(res) cnt_mx = 9;
else cnt_mx = 0;
} else {
cur_mn = val;
cnt_mx = 11;
return;
}
} else if(cnt_mx == 11) {
cur_mn_idx = val;
if(res) cnt_mx = 9;
else cnt_mx = 0;
}
lst_mn += cur_mn;
int u = cur_mn_idx;
flag[u] = true;
d[u] = lst_mn;
for(auto p : E[u]) {
int v = p.fi, w = p.se;
d[v] = std::min(d[v], d[u] + w);
}
cur_mn = CINF;
for(int i = 0; i < N; ++i)
if(!flag[i] && cur_mn > d[i] - lst_mn) {
cur_mn = d[i] - lst_mn;
cur_mn_idx = i;
}
if(cur_mn != CINF) {
for(int i = 0; i < 9; ++i)
SendB((cur_mn >> i) & 1);
}
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 3820kb
input:
1 1 1 1 1 1 1 1 1 -1 -1 -1
output:
-1 0 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 1 0 0 1 1 1 1 0 0 0 1 0 -1 -1
input:
output:
0 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1...
result:
wrong answer 2nd lines differ - expected: '2417', found: '1073741823'
Subtask #2:
score: 0
Wrong Answer
Test #7:
score: 0
Wrong Answer
time: 2ms
memory: 3688kb
input:
1 1 1 1 1 1 1 1 1 -1 -1 -1
output:
-1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 -1 -1
input:
output:
511
result:
wrong answer 1st lines differ - expected: '0', found: '511'
Subtask #3:
score: 0
Wrong Answer
Test #14:
score: 8
Accepted
time: 14ms
memory: 3860kb
input:
1 0 0 1 1 1 0 0 1 -1 1 1 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 -1 1 1 1 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 -1 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 1 0 1 -1 1 1 1 0 1 1 0 0 1 -1 1 1 0 1 1 1 0 1 0 -1 0 0 1 1 0 0 0 1 0 -1 0 0 1 1 1 1 0 0 0 -1 1 0 1 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 1 1 0 0 0 0 -1 0 1 1...
output:
-1 1 0 1 0 0 1 0 1 1 -1 0 0 1 1 0 1 1 0 0 -1 0 1 0 1 0 1 1 0 0 -1 1 0 1 1 1 0 0 0 0 1 0 1 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 -1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 1 0 1 0 0 0 -1 1 1 1 0 1 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0 -1 1 1 0 1 0 1 0 0 0 1 1 1 1 1 1 0 1 0 0 0 -1 1 0 0 0 1 0 1 1 0 1 1 1 1 1 1 0 1 0 0 0 -1 0...
input:
output:
0 3328 4161 4895 4209 3745 3720 4315 3313 4008 2104 3319 3666 3501 3499 3359 4244 3853 1906 392 2028 3840 3209 2376 3001 5530 2494 3340 5583 3653 3624 3798 4121 2243 4252 2165 4289 2935 6032 5124 5255 1362 3336 5054 4411 6329 4444 2299 2294 3848 5170 3200 1544 3953 3577 5969 6227 3533 4569 2619 2738...
result:
ok 2000 lines
Test #15:
score: 0
Wrong Answer
time: 2ms
memory: 3756kb
input:
1 1 1 1 1 1 1 1 1 -1 -1 -1
output:
-1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 -1 -1
input:
output:
511
result:
wrong answer 1st lines differ - expected: '0', found: '511'
Subtask #4:
score: 0
Wrong Answer
Test #24:
score: 0
Wrong Answer
time: 2ms
memory: 3776kb
input:
1 1 1 1 1 1 1 1 1 -1 -1 -1
output:
-1 1 1 0 0 1 0 0 1 0 1 0 0 0 1 0 0 1 1 0 0 0 1 1 1 0 1 1 1 0 -1 -1
input:
output:
0 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1...
result:
wrong answer 2nd lines differ - expected: '1881', found: '1073741823'
Subtask #5:
score: 0
Wrong Answer
Test #38:
score: 0
Wrong Answer
time: 2ms
memory: 3768kb
input:
0 1 1 1 1 0 1 0 0 -1 0 0 1 1 1 1 0 1 1 1 0 -1 -1 -1
output:
-1 1 1 1 1 1 1 1 1 1 -1 1 0 1 1 0 1 1 0 1 -1 -1
input:
output:
0 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1...
result:
wrong answer 2nd lines differ - expected: '3467', found: '1073741823'
Subtask #6:
score: 0
Wrong Answer
Test #51:
score: 0
Wrong Answer
time: 2ms
memory: 3740kb
input:
1 1 1 1 1 1 1 1 1 -1 -1 -1
output:
-1 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 0 1 0 1 0 0 1 0 1 0 0 1 0 1 -1 -1
input:
output:
0 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1...
result:
wrong answer 2nd lines differ - expected: '4745', found: '1073741823'
Subtask #7:
score: 0
Wrong Answer
Test #64:
score: 16
Accepted
time: 27ms
memory: 3952kb
input:
0 0 0 0 1 1 1 1 1 -1 0 0 1 0 1 1 1 0 0 0 1 0 1 1 1 1 0 0 0 1 -1 1 1 0 0 1 1 0 0 0 0 1 1 1 1 0 1 0 1 1 1 -1 1 1 0 1 1 0 1 0 0 1 0 0 1 1 0 0 1 1 0 0 -1 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 1 1 1 1 0 -1 0 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 0 -1 0 1 0 1 0 1 0 0 0 0 0 1 1 1 0 1 0 1 1 1 -1 0 1 0 0 1 1 1 0 1 1 1...
output:
-1 1 1 0 0 1 1 1 1 1 -1 1 1 0 0 1 1 1 1 1 -1 1 1 0 0 1 1 1 1 1 -1 0 0 1 0 1 0 0 0 1 -1 1 1 0 0 1 0 0 0 1 -1 1 1 1 1 1 1 1 0 0 -1 1 0 0 1 0 1 1 1 1 -1 1 1 0 1 1 1 1 1 0 -1 0 0 0 0 0 0 0 1 1 -1 0 1 1 0 0 1 1 1 1 -1 1 0 0 0 0 0 0 1 0 -1 0 1 1 1 0 1 0 1 1 -1 0 0 1 0 1 0 1 1 1 -1 1 0 1 1 0 0 0 1 1 -1 1 0...
input:
output:
0 25855 513884 451446 379664 463677 147972 259014 115396 537065 61376 510191 95200 328777 282337 199131 72153 405843 215292 529082 413220 99569 275396 215884 52889 281825 182731 64473 510973 545141 417123 190844 319517 483688 15462 490221 521781 384795 539004 457181 146029 122086 1730 31958 265013 7...
result:
ok 2000 lines
Test #65:
score: 16
Accepted
time: 95ms
memory: 19104kb
input:
1 1 1 1 0 1 0 0 0 -1 1 0 1 0 1 0 0 0 0 -1 1 1 1 1 0 0 0 0 0 -1 1 0 0 1 0 0 0 0 0 -1 1 1 1 0 0 0 0 0 0 -1 0 1 0 1 1 0 0 0 0 -1 1 0 0 1 1 0 0 0 0 -1 0 0 1 0 1 0 0 0 0 -1 0 1 1 1 0 0 0 0 0 -1 0 0 0 1 0 0 0 0 0 -1 1 1 1 0 1 0 0 0 0 -1 1 0 0 0 1 0 0 0 0 -1 1 1 0 1 1 0 0 0 0 -1 0 1 1 0 1 0 0 0 0 -1 0 0 1 ...
output:
-1 1 1 0 0 0 0 0 0 0 0 1 0 0 1 1 1 1 0 1 0 0 1 1 0 0 0 0 0 0 -1 0 0 0 1 1 1 1 1 1 0 1 0 1 1 0 0 0 0 0 0 -1 0 0 1 0 1 1 1 0 1 0 1 0 1 0 0 0 0 0 0 0 -1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 -1 0 0 1 1 1 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 -1 0 0 1 1 1 1 0 1 1 0 0 1 0 1 0 0 0 0 0 0 -1 1 0 1 1 1 0 1 0 1 1 1...
input:
output:
0 6187 1398 17 6163 4742 4598 2337 2237 6475 6001 5268 2245 6132 4925 1482 4253 1962 6642 2449 2704 3396 5449 2492 706 835 1879 3203 6855 4265 546 1231 2390 2300 4651 1353 1673 6724 6753 360 4275 6749 3400 1385 2945 6010 5339 226 2511 4558 1033 4708 4330 1882 1185 3535 5071 3843 1252 110 6571 6727 3...
result:
ok 2000 lines
Test #66:
score: 16
Accepted
time: 83ms
memory: 17412kb
input:
0 1 1 0 0 0 0 0 0 -1 0 1 0 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 -1 0 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 0 1 0 0 0 0 -1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 1 0 1 0 0 0 0 -1 1 1 1 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 0 0 -1 1 1 0 0 0 0 0 0 0 1 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0...
output:
-1 0 0 1 0 1 0 1 0 0 -1 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 1 0 0 0 0 0 0 1 0 0 0 -1 1 1 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 1 1 0 0 1 0 0 0 0 -1 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 1 1 0 1 1 0 0 0 0 0 -1 1 0 1 0 0 0 0 0 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 1 1 0 0 0 0 -1 1 1 1 0 0 0 0 0 0 1 1 0 1 1 0 1 ...
input:
output:
0 5455 4313 3996 4463 4115 2413 1141 7939 4669 5854 7806 7612 3394 7713 441 4956 1630 751 2070 4241 6754 3518 3736 3158 549 4590 6798 842 1597 7637 3679 6104 7953 5654 3951 1877 2075 5983 6633 5724 2967 2362 527 7670 3759 3471 4089 508 1187 5437 3533 3003 7429 7499 5966 7484 949 1545 1862 542 3370 1...
result:
ok 2000 lines
Test #67:
score: 0
Wrong Answer
time: 0ms
memory: 3924kb
input:
1 1 1 1 1 1 1 1 1 -1 1 0 0 1 1 0 1 1 0 -1 0 1 0 0 1 0 1 1 0 -1 1 0 1 0 1 1 0 0 0 1 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 1 1 0 1 -1 0 0 1 1 0 0 0 0 1 -1 0 0 0 0 0 1 1 0 0 -1 0 0 0 0 0 0 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 0 1 1 0 0 -1 0 1 0 0 1 0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 1 0 0 0 1 0 0 -1 1 0 0 0 1 1 ...
output:
-1 0 1 1 0 0 1 0 0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 -1 1 1 0 0 1 1 0 0 0 0 1 1 1 1 0 1 0 0 0 0 -1 0 1 1 1 1 1 0 0 0 0 1 1 0 1 1 1 0 0 1 0 -1 0 0 0 1 0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 1 0 1 1 1 0 1 1 0 0 -1 1 1 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 -1 0 0 0 1 1 0 1 0 1 0 0 1 0 0 1 1 0 1 0 0 -1 1 0...
input:
output:
0 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1...
result:
wrong answer 2nd lines differ - expected: '79964', found: '1073741823'