#include "Azer.h"
#include <vector>
#include <queue>
#include <cstdio>
using namespace std;
typedef pair<int,int> ii;
namespace {
const int MAXN = 2003;
int n;
bool done[MAXN];
int dc=0;
vector<int> solA;
priority_queue<ii> e;
vector<ii> graph[MAXN];
int pre=0;
int idx=0;
int cA, cB;
int nA, nB;
void add_node(int val, int node){
//printf("A add_node(%d %d)\n", val, node);
pre = val;
solA[node] = val;
done[node] = true;
dc++;
for(auto i:graph[node]){
e.push(ii(-solA[node] + i.first, i.second));
}
}
void send_best(){
if(dc == n) return;
cA = (1<<9)-1;
nA = -1;
while(!e.empty() && done[e.top().second]) e.pop();
if(!e.empty()){
cA = (-e.top().first) - pre;
nA = e.top().second;
}
//printf("A send_best() -> %d\n", cA);
for(int i=0;i<9;++i) SendA((1<<i) & cA);
}
}
void InitA(int n, int a, vector<int> u, vector<int> v, vector<int> c) {
::n = n;
solA.resize(n);
for(int i=0;i<a;++i){
graph[u[i]].push_back(ii(-c[i], v[i]));
graph[v[i]].push_back(ii(-c[i], u[i]));
}
add_node(0, 0);
send_best();
}
void ReceiveA(bool x) {
if(idx<9){
cB |= ((int)x) << idx;
idx++;
if(idx == 9){
//printf("A recieved cB %d\n", cB);
if(cB > cA){
add_node(pre + cA, nA);
for(int i = 0; i < 11; i++){
SendA((1<<i) & nA);
}
idx = 0;
cB = 0; nB = 0;
send_best();
}
}
}else{
nB |= ((int)x) << (idx - 9);
idx++;
if(idx == 20){
//printf("A recieved nB %d\n", nB);
add_node(pre + cB, nB);
idx = 0;
cB = 0; nB = 0;
send_best();
}
}
}
std::vector<int> Answer() {
return vector<int>(solA);
}
#include "Baijan.h"
#include <vector>
#include <queue>
#include <cstdio>
#ifdef EVAL
#define dbg(x) ;
#else
#define dbg(x) //printf(x)
#endif
using namespace std;
typedef pair<int,int> ii;
namespace {
const int MAXN = 2003;
int n;
bool done[MAXN];
int dc=0;
vector<int> solB;
priority_queue<ii> e;
vector<ii> graph[MAXN];
int pre=0;
int idx=0;
int cA, cB;
int nA, nB;
void add_node(int val, int node){
//printf("B add_node(%d %d)\n", val, node);
pre = val;
solB[node] = val;
done[node] = true;
dc++;
for(auto i:graph[node]){
e.push(ii(-solB[node] + i.first, i.second));
}
}
void send_best(){
if(dc == n) return;
cB = (1<<9)-1;
nB = -1;
while(!e.empty() && done[e.top().second]) e.pop();
if(!e.empty()){
cB = (-e.top().first) - pre;
nB = e.top().second;
}
//printf("B send_best() -> %d\n", cB);
for(int i=0;i<9;++i) SendB((1<<i) & cB);
}
}
void InitB(int n, int a, vector<int> u, vector<int> v, vector<int> c) {
::n = n;
solB.resize(n);
for(int i=0;i<a;++i){
graph[u[i]].push_back(ii(-c[i], v[i]));
graph[v[i]].push_back(ii(-c[i], u[i]));
}
add_node(0, 0);
}
void ReceiveB(bool x) {
if(idx<9){
cA |= ((int)x) << idx;
idx++;
if(idx == 9){
//printf("B recieved cA %d\n", cA);
send_best();
if(cA >= cB){
add_node(pre + cB, nB);
for(int i = 0; i < 11; i++){
SendB((1<<i) & nB);
}
idx = 0;
cA = 0; nA = 0;
}
}
}else{
nA |= ((int)x) << (idx - 9);
idx++;
if(idx == 20){
//printf("B recieved nA %d\n", nA);
add_node(pre + cA, nA);
idx = 0;
cA = 0; nA = 0;
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1200 ms |
2048 KB |
Output is correct |
2 |
Correct |
16 ms |
1536 KB |
Output is correct |
3 |
Correct |
1200 ms |
1624 KB |
Output is correct |
4 |
Correct |
1242 ms |
20208 KB |
Output is correct |
5 |
Correct |
72 ms |
2024 KB |
Output is correct |
6 |
Correct |
1108 ms |
5656 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
1280 KB |
Output is correct |
2 |
Correct |
1086 ms |
1536 KB |
Output is correct |
3 |
Correct |
1024 ms |
2048 KB |
Output is correct |
4 |
Correct |
1902 ms |
55088 KB |
Output is correct |
5 |
Correct |
1488 ms |
56976 KB |
Output is correct |
6 |
Correct |
220 ms |
1840 KB |
Output is correct |
7 |
Correct |
1432 ms |
57376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
878 ms |
1792 KB |
Output is correct |
2 |
Correct |
17 ms |
1320 KB |
Output is correct |
3 |
Correct |
983 ms |
1760 KB |
Output is correct |
4 |
Correct |
1178 ms |
2048 KB |
Output is correct |
5 |
Correct |
1034 ms |
1792 KB |
Output is correct |
6 |
Correct |
1082 ms |
1792 KB |
Output is correct |
7 |
Correct |
966 ms |
1536 KB |
Output is correct |
8 |
Correct |
1130 ms |
1672 KB |
Output is correct |
9 |
Correct |
1078 ms |
1536 KB |
Output is correct |
10 |
Correct |
1132 ms |
1792 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
479 ms |
1536 KB |
Output is correct |
2 |
Correct |
568 ms |
1536 KB |
Output is correct |
3 |
Correct |
948 ms |
24088 KB |
Output is correct |
4 |
Correct |
504 ms |
1792 KB |
Output is correct |
5 |
Correct |
904 ms |
17736 KB |
Output is correct |
6 |
Correct |
556 ms |
1792 KB |
Output is correct |
7 |
Correct |
600 ms |
1792 KB |
Output is correct |
8 |
Correct |
530 ms |
1536 KB |
Output is correct |
9 |
Correct |
994 ms |
47184 KB |
Output is correct |
10 |
Correct |
912 ms |
47080 KB |
Output is correct |
11 |
Correct |
1410 ms |
85424 KB |
Output is correct |
12 |
Correct |
1108 ms |
79896 KB |
Output is correct |
13 |
Correct |
378 ms |
1944 KB |
Output is correct |
14 |
Correct |
16 ms |
1280 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
479 ms |
1536 KB |
Output is correct |
2 |
Correct |
568 ms |
1536 KB |
Output is correct |
3 |
Correct |
948 ms |
24088 KB |
Output is correct |
4 |
Correct |
504 ms |
1792 KB |
Output is correct |
5 |
Correct |
904 ms |
17736 KB |
Output is correct |
6 |
Correct |
556 ms |
1792 KB |
Output is correct |
7 |
Correct |
600 ms |
1792 KB |
Output is correct |
8 |
Correct |
530 ms |
1536 KB |
Output is correct |
9 |
Correct |
994 ms |
47184 KB |
Output is correct |
10 |
Correct |
912 ms |
47080 KB |
Output is correct |
11 |
Correct |
1410 ms |
85424 KB |
Output is correct |
12 |
Correct |
1108 ms |
79896 KB |
Output is correct |
13 |
Correct |
378 ms |
1944 KB |
Output is correct |
14 |
Correct |
16 ms |
1280 KB |
Output is correct |
15 |
Correct |
730 ms |
1792 KB |
Output is correct |
16 |
Correct |
622 ms |
1280 KB |
Output is correct |
17 |
Correct |
500 ms |
1280 KB |
Output is correct |
18 |
Correct |
882 ms |
17752 KB |
Output is correct |
19 |
Correct |
572 ms |
1376 KB |
Output is correct |
20 |
Correct |
916 ms |
18280 KB |
Output is correct |
21 |
Correct |
745 ms |
1568 KB |
Output is correct |
22 |
Correct |
656 ms |
1792 KB |
Output is correct |
23 |
Correct |
1108 ms |
52888 KB |
Output is correct |
24 |
Correct |
1060 ms |
52624 KB |
Output is correct |
25 |
Correct |
1494 ms |
102704 KB |
Output is correct |
26 |
Correct |
1362 ms |
89064 KB |
Output is correct |
27 |
Correct |
596 ms |
2136 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
479 ms |
1536 KB |
Output is correct |
2 |
Correct |
568 ms |
1536 KB |
Output is correct |
3 |
Correct |
948 ms |
24088 KB |
Output is correct |
4 |
Correct |
504 ms |
1792 KB |
Output is correct |
5 |
Correct |
904 ms |
17736 KB |
Output is correct |
6 |
Correct |
556 ms |
1792 KB |
Output is correct |
7 |
Correct |
600 ms |
1792 KB |
Output is correct |
8 |
Correct |
530 ms |
1536 KB |
Output is correct |
9 |
Correct |
994 ms |
47184 KB |
Output is correct |
10 |
Correct |
912 ms |
47080 KB |
Output is correct |
11 |
Correct |
1410 ms |
85424 KB |
Output is correct |
12 |
Correct |
1108 ms |
79896 KB |
Output is correct |
13 |
Correct |
378 ms |
1944 KB |
Output is correct |
14 |
Correct |
16 ms |
1280 KB |
Output is correct |
15 |
Correct |
730 ms |
1792 KB |
Output is correct |
16 |
Correct |
622 ms |
1280 KB |
Output is correct |
17 |
Correct |
500 ms |
1280 KB |
Output is correct |
18 |
Correct |
882 ms |
17752 KB |
Output is correct |
19 |
Correct |
572 ms |
1376 KB |
Output is correct |
20 |
Correct |
916 ms |
18280 KB |
Output is correct |
21 |
Correct |
745 ms |
1568 KB |
Output is correct |
22 |
Correct |
656 ms |
1792 KB |
Output is correct |
23 |
Correct |
1108 ms |
52888 KB |
Output is correct |
24 |
Correct |
1060 ms |
52624 KB |
Output is correct |
25 |
Correct |
1494 ms |
102704 KB |
Output is correct |
26 |
Correct |
1362 ms |
89064 KB |
Output is correct |
27 |
Correct |
596 ms |
2136 KB |
Output is correct |
28 |
Correct |
942 ms |
1768 KB |
Output is correct |
29 |
Correct |
504 ms |
1736 KB |
Output is correct |
30 |
Correct |
1498 ms |
43920 KB |
Output is correct |
31 |
Correct |
956 ms |
1600 KB |
Output is correct |
32 |
Correct |
1180 ms |
37416 KB |
Output is correct |
33 |
Correct |
744 ms |
2048 KB |
Output is correct |
34 |
Correct |
652 ms |
2048 KB |
Output is correct |
35 |
Correct |
816 ms |
1792 KB |
Output is correct |
36 |
Correct |
1218 ms |
58072 KB |
Output is correct |
37 |
Correct |
1118 ms |
58344 KB |
Output is correct |
38 |
Correct |
1714 ms |
113712 KB |
Output is correct |
39 |
Correct |
1604 ms |
102264 KB |
Output is correct |
40 |
Correct |
846 ms |
2352 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1200 ms |
2048 KB |
Output is correct |
2 |
Correct |
16 ms |
1536 KB |
Output is correct |
3 |
Correct |
1200 ms |
1624 KB |
Output is correct |
4 |
Correct |
1242 ms |
20208 KB |
Output is correct |
5 |
Correct |
72 ms |
2024 KB |
Output is correct |
6 |
Correct |
1108 ms |
5656 KB |
Output is correct |
7 |
Correct |
16 ms |
1280 KB |
Output is correct |
8 |
Correct |
1086 ms |
1536 KB |
Output is correct |
9 |
Correct |
1024 ms |
2048 KB |
Output is correct |
10 |
Correct |
1902 ms |
55088 KB |
Output is correct |
11 |
Correct |
1488 ms |
56976 KB |
Output is correct |
12 |
Correct |
220 ms |
1840 KB |
Output is correct |
13 |
Correct |
1432 ms |
57376 KB |
Output is correct |
14 |
Correct |
878 ms |
1792 KB |
Output is correct |
15 |
Correct |
17 ms |
1320 KB |
Output is correct |
16 |
Correct |
983 ms |
1760 KB |
Output is correct |
17 |
Correct |
1178 ms |
2048 KB |
Output is correct |
18 |
Correct |
1034 ms |
1792 KB |
Output is correct |
19 |
Correct |
1082 ms |
1792 KB |
Output is correct |
20 |
Correct |
966 ms |
1536 KB |
Output is correct |
21 |
Correct |
1130 ms |
1672 KB |
Output is correct |
22 |
Correct |
1078 ms |
1536 KB |
Output is correct |
23 |
Correct |
1132 ms |
1792 KB |
Output is correct |
24 |
Correct |
479 ms |
1536 KB |
Output is correct |
25 |
Correct |
568 ms |
1536 KB |
Output is correct |
26 |
Correct |
948 ms |
24088 KB |
Output is correct |
27 |
Correct |
504 ms |
1792 KB |
Output is correct |
28 |
Correct |
904 ms |
17736 KB |
Output is correct |
29 |
Correct |
556 ms |
1792 KB |
Output is correct |
30 |
Correct |
600 ms |
1792 KB |
Output is correct |
31 |
Correct |
530 ms |
1536 KB |
Output is correct |
32 |
Correct |
994 ms |
47184 KB |
Output is correct |
33 |
Correct |
912 ms |
47080 KB |
Output is correct |
34 |
Correct |
1410 ms |
85424 KB |
Output is correct |
35 |
Correct |
1108 ms |
79896 KB |
Output is correct |
36 |
Correct |
378 ms |
1944 KB |
Output is correct |
37 |
Correct |
16 ms |
1280 KB |
Output is correct |
38 |
Correct |
730 ms |
1792 KB |
Output is correct |
39 |
Correct |
622 ms |
1280 KB |
Output is correct |
40 |
Correct |
500 ms |
1280 KB |
Output is correct |
41 |
Correct |
882 ms |
17752 KB |
Output is correct |
42 |
Correct |
572 ms |
1376 KB |
Output is correct |
43 |
Correct |
916 ms |
18280 KB |
Output is correct |
44 |
Correct |
745 ms |
1568 KB |
Output is correct |
45 |
Correct |
656 ms |
1792 KB |
Output is correct |
46 |
Correct |
1108 ms |
52888 KB |
Output is correct |
47 |
Correct |
1060 ms |
52624 KB |
Output is correct |
48 |
Correct |
1494 ms |
102704 KB |
Output is correct |
49 |
Correct |
1362 ms |
89064 KB |
Output is correct |
50 |
Correct |
596 ms |
2136 KB |
Output is correct |
51 |
Correct |
942 ms |
1768 KB |
Output is correct |
52 |
Correct |
504 ms |
1736 KB |
Output is correct |
53 |
Correct |
1498 ms |
43920 KB |
Output is correct |
54 |
Correct |
956 ms |
1600 KB |
Output is correct |
55 |
Correct |
1180 ms |
37416 KB |
Output is correct |
56 |
Correct |
744 ms |
2048 KB |
Output is correct |
57 |
Correct |
652 ms |
2048 KB |
Output is correct |
58 |
Correct |
816 ms |
1792 KB |
Output is correct |
59 |
Correct |
1218 ms |
58072 KB |
Output is correct |
60 |
Correct |
1118 ms |
58344 KB |
Output is correct |
61 |
Correct |
1714 ms |
113712 KB |
Output is correct |
62 |
Correct |
1604 ms |
102264 KB |
Output is correct |
63 |
Correct |
846 ms |
2352 KB |
Output is correct |
64 |
Correct |
1038 ms |
2048 KB |
Output is correct |
65 |
Correct |
1710 ms |
47528 KB |
Output is correct |
66 |
Correct |
1628 ms |
41360 KB |
Output is correct |
67 |
Correct |
1090 ms |
2048 KB |
Output is correct |
68 |
Correct |
1242 ms |
2048 KB |
Output is correct |
69 |
Correct |
1888 ms |
111032 KB |
Output is correct |
70 |
Correct |
1914 ms |
94016 KB |
Output is correct |
71 |
Correct |
1136 ms |
12768 KB |
Output is correct |
72 |
Correct |
1073 ms |
3240 KB |
Output is correct |