#include <bits/stdc++.h>
#include "Azer.h"
#define ff first
#define ss second
using namespace std;
struct Compare {
bool operator()(pair<int,int> a, pair<int,int> b) {
return a > b;
}
};
int GETTING_VAL= 0;
int GETTING_V = 1;
int ans[2001];
int n,m;
vector<pair<int,int>> graf[2001];
priority_queue<pair<int,int>, vector<pair<int,int>>, Compare> pri;
int akt_odl;
int oper;
int how_many_bits;
int num;
int new_v;
int tryb;
void SendNum(int x, int wiel)
{
for(int bit = 0; bit < wiel; bit++)
{
if(x & (1 << bit))
{
SendA(1);
}
else
{
SendA(0);
}
}
}
void InitA(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> C)
{
// odw[0] = 1;
ans[0] = 0;
n = N;
m = M;
for(int i = 0; i < m; i++)
{
graf[U[i]].push_back({C[i],V[i]});
graf[V[i]].push_back({C[i],U[i]});
}
for(auto& it: graf[0])
{
pri.push(it);
}
pri.push({1e9,2000});
pair<int,int> t = pri.top();
SendNum(min(t.ff - akt_odl,501),9);
}
void ReceiveA(bool x)
{
if(tryb == GETTING_VAL)
{
if(x) num += (1 << how_many_bits);
how_many_bits++;
if(how_many_bits == 9)
{
oper++;
if(oper == n) return;
while((int)pri.size() != 0 && (ans[pri.top().ss] != 0 || pri.top().ss == 0)) pri.pop();
if(pri.size() == 0) pri.push({1e9,2000});
//cout << num << " val A\n";
//cout << "ja: " << pri.top().ff - akt_odl << ", B: " << num << " akt_odl:"<< akt_odl<<"\n";
if((pri.top().ff - akt_odl <= num && pri.top().ff != 1e9) || num == 501)
{
// cout << "Sending to B: " << pri.top().ss << " info about v\n";
SendNum(pri.top().ss,11);
akt_odl = pri.top().ff;
ans[pri.top().ss] = akt_odl;
for(auto& it: graf[pri.top().ss])
{
pri.push({it.ff + akt_odl, it.ss});
}
how_many_bits = 0;
num = 0;
pri.pop();
while((int)pri.size() != 0 && (ans[pri.top().ss] != 0 || pri.top().ss == 0)) pri.pop();
if(pri.size() == 0) pri.push({1e9,2000});
// cout << "Sending to B: " << min(pri.top().ff - akt_odl,501) << " info about min\n";
SendNum(min(pri.top().ff - akt_odl,501),9); //only for Azer
}
else
{
new_v = 0;
how_many_bits = 0;
tryb = GETTING_V;
}
}
}
else
{
if(x) new_v += (1 << how_many_bits);
how_many_bits++;
if(how_many_bits == 11)
{
// cout << new_v << "new_v A\n";
tryb = GETTING_VAL;
ans[new_v] = akt_odl+num;
akt_odl += num;
//odw[new_v] = 1;
// cout << akt_odl << " akt_odl A\n";
for(auto& it: graf[new_v])
{
pri.push({it.ff + akt_odl, it.ss});
}
how_many_bits = 0;
num = 0;
while((int)pri.size() != 0 && (ans[pri.top().ss] != 0 || pri.top().ss == 0)) pri.pop();
if(pri.size() == 0) pri.push({1e9,2000});
// cout << "Sending to B: " << min(pri.top().ff - akt_odl,501) << " info about min\n";
SendNum(min(pri.top().ff - akt_odl,501),9);
}
}
}
vector<int> Answer()
{
vector<int> ans2;
for(int i = 0; i < n; i++) ans2.push_back(ans[i]);
return ans2;
}
#include <bits/stdc++.h>
#include "Baijan.h"
#define ff first
#define ss second
using namespace std;
namespace {
struct Compare {
bool operator()(pair<int,int> a, pair<int,int> b) {
return a > b;
}
};
int GETTING_VAL= 0;
int GETTING_V = 1;
int ans[2001];
int n,m;
vector<pair<int,int>> graf[2001];
priority_queue<pair<int,int>, vector<pair<int,int>>, Compare> pri;
int akt_odl;
int oper;
int how_many_bits;
int num;
int new_v;
int tryb;
void SendNum(int x, int wiel)
{
for(int bit = 0; bit < wiel; bit++)
{
if(x & (1 << bit))
{
SendB(1);
}
else
{
SendB(0);
}
}
}
}
void InitB(int N, int M, vector<int> U, vector<int> V, vector<int> cost)
{
ans[0] = 0;
n = N;
m = M;
for(int i = 0; i < m; i++)
{
graf[U[i]].push_back({cost[i],V[i]});
graf[V[i]].push_back({cost[i],U[i]});
}
for(auto& it: graf[0])
{
pri.push(it);
}
pri.push({1e9,2000});
pair<int,int> t = pri.top();
SendNum(min(t.ff - akt_odl,501),9);
}
void ReceiveB(bool x)
{
if(tryb == GETTING_VAL)
{
if(x) num += (1 << how_many_bits);
how_many_bits++;
if(how_many_bits == 9)
{
// cout << num << " val B\n";
oper++;
if(oper == n) return;
while((int)pri.size() != 0 && (ans[pri.top().ss] != 0 || pri.top().ss == 0)) pri.pop();
if(pri.size() == 0) pri.push({1e9,2000});
// cout << "ja: " << pri.top().ff - akt_odl << ", A: " << num << " akt_odl:"<< akt_odl<<"\n";
if((pri.top().ff - akt_odl < num && pri.top().ff != 1e9)|| num == 501)
{
// cout << "Sending to A: " << pri.top().ss << " info about v\n";
SendNum(pri.top().ss,11);
akt_odl = pri.top().ff;
ans[pri.top().ss] = akt_odl;
for(auto& it: graf[pri.top().ss])
{
pri.push({it.ff + akt_odl, it.ss});
}
how_many_bits = 0;
num = 0;
pri.pop();
while((int)pri.size() != 0 && (ans[pri.top().ss] != 0 || pri.top().ss == 0)) pri.pop();
if(pri.size() == 0) pri.push({1e9,2000});
//cout << "Sending to A: " << min(pri.top().ff - akt_odl,501) << " info about min\n";
SendNum(min(pri.top().ff - akt_odl,501),9); //only for Azer
}
else
{
new_v = 0;
how_many_bits = 0;
tryb = GETTING_V;
}
}
}
else
{
if(x) new_v += (1 << how_many_bits);
how_many_bits++;
if(how_many_bits == 11)
{
//cout << new_v << "new_v B\n";
tryb = GETTING_VAL;
ans[new_v] = akt_odl+num;
akt_odl += num;
for(auto& it: graf[new_v])
{
pri.push({it.ff + akt_odl, it.ss});
// cout << it.ss << " nowy B\n";
}
how_many_bits = 0;
num = 0;
while((int)pri.size() != 0 && (ans[pri.top().ss] != 0 || pri.top().ss == 0)) pri.pop();
if(pri.size() == 0) pri.push({1e9,2000});
// cout << pri.top().ss << " nowy_max B\n";
// cout << "Sending to A: " << min(pri.top().ff - akt_odl,501) << " info about min\n";
SendNum(min(pri.top().ff - akt_odl,501),9);
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
421 ms |
1076 KB |
Output is correct |
2 |
Correct |
0 ms |
664 KB |
Output is correct |
3 |
Correct |
318 ms |
1084 KB |
Output is correct |
4 |
Correct |
456 ms |
10260 KB |
Output is correct |
5 |
Correct |
12 ms |
2100 KB |
Output is correct |
6 |
Correct |
362 ms |
3436 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
664 KB |
Output is correct |
2 |
Correct |
420 ms |
1124 KB |
Output is correct |
3 |
Correct |
376 ms |
1200 KB |
Output is correct |
4 |
Correct |
698 ms |
28040 KB |
Output is correct |
5 |
Correct |
703 ms |
29544 KB |
Output is correct |
6 |
Correct |
61 ms |
788 KB |
Output is correct |
7 |
Correct |
659 ms |
30876 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
333 ms |
1388 KB |
Output is correct |
2 |
Correct |
1 ms |
664 KB |
Output is correct |
3 |
Correct |
316 ms |
1068 KB |
Output is correct |
4 |
Correct |
410 ms |
1148 KB |
Output is correct |
5 |
Correct |
346 ms |
1148 KB |
Output is correct |
6 |
Correct |
317 ms |
1092 KB |
Output is correct |
7 |
Correct |
406 ms |
1152 KB |
Output is correct |
8 |
Correct |
364 ms |
1060 KB |
Output is correct |
9 |
Correct |
406 ms |
1056 KB |
Output is correct |
10 |
Correct |
418 ms |
1084 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
135 ms |
816 KB |
Output is correct |
2 |
Correct |
194 ms |
792 KB |
Output is correct |
3 |
Correct |
301 ms |
13448 KB |
Output is correct |
4 |
Correct |
144 ms |
844 KB |
Output is correct |
5 |
Correct |
210 ms |
10364 KB |
Output is correct |
6 |
Correct |
114 ms |
844 KB |
Output is correct |
7 |
Correct |
173 ms |
664 KB |
Output is correct |
8 |
Correct |
135 ms |
1108 KB |
Output is correct |
9 |
Correct |
375 ms |
25428 KB |
Output is correct |
10 |
Correct |
400 ms |
24504 KB |
Output is correct |
11 |
Correct |
599 ms |
48600 KB |
Output is correct |
12 |
Correct |
507 ms |
46316 KB |
Output is correct |
13 |
Correct |
163 ms |
1088 KB |
Output is correct |
14 |
Correct |
0 ms |
916 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
135 ms |
816 KB |
Output is correct |
2 |
Correct |
194 ms |
792 KB |
Output is correct |
3 |
Correct |
301 ms |
13448 KB |
Output is correct |
4 |
Correct |
144 ms |
844 KB |
Output is correct |
5 |
Correct |
210 ms |
10364 KB |
Output is correct |
6 |
Correct |
114 ms |
844 KB |
Output is correct |
7 |
Correct |
173 ms |
664 KB |
Output is correct |
8 |
Correct |
135 ms |
1108 KB |
Output is correct |
9 |
Correct |
375 ms |
25428 KB |
Output is correct |
10 |
Correct |
400 ms |
24504 KB |
Output is correct |
11 |
Correct |
599 ms |
48600 KB |
Output is correct |
12 |
Correct |
507 ms |
46316 KB |
Output is correct |
13 |
Correct |
163 ms |
1088 KB |
Output is correct |
14 |
Correct |
0 ms |
916 KB |
Output is correct |
15 |
Correct |
247 ms |
1020 KB |
Output is correct |
16 |
Correct |
158 ms |
1124 KB |
Output is correct |
17 |
Correct |
170 ms |
1124 KB |
Output is correct |
18 |
Correct |
282 ms |
10164 KB |
Output is correct |
19 |
Correct |
155 ms |
1128 KB |
Output is correct |
20 |
Correct |
319 ms |
10708 KB |
Output is correct |
21 |
Correct |
166 ms |
1140 KB |
Output is correct |
22 |
Correct |
216 ms |
888 KB |
Output is correct |
23 |
Correct |
461 ms |
27928 KB |
Output is correct |
24 |
Correct |
428 ms |
28604 KB |
Output is correct |
25 |
Correct |
769 ms |
56608 KB |
Output is correct |
26 |
Correct |
635 ms |
50712 KB |
Output is correct |
27 |
Correct |
174 ms |
1160 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
135 ms |
816 KB |
Output is correct |
2 |
Correct |
194 ms |
792 KB |
Output is correct |
3 |
Correct |
301 ms |
13448 KB |
Output is correct |
4 |
Correct |
144 ms |
844 KB |
Output is correct |
5 |
Correct |
210 ms |
10364 KB |
Output is correct |
6 |
Correct |
114 ms |
844 KB |
Output is correct |
7 |
Correct |
173 ms |
664 KB |
Output is correct |
8 |
Correct |
135 ms |
1108 KB |
Output is correct |
9 |
Correct |
375 ms |
25428 KB |
Output is correct |
10 |
Correct |
400 ms |
24504 KB |
Output is correct |
11 |
Correct |
599 ms |
48600 KB |
Output is correct |
12 |
Correct |
507 ms |
46316 KB |
Output is correct |
13 |
Correct |
163 ms |
1088 KB |
Output is correct |
14 |
Correct |
0 ms |
916 KB |
Output is correct |
15 |
Correct |
247 ms |
1020 KB |
Output is correct |
16 |
Correct |
158 ms |
1124 KB |
Output is correct |
17 |
Correct |
170 ms |
1124 KB |
Output is correct |
18 |
Correct |
282 ms |
10164 KB |
Output is correct |
19 |
Correct |
155 ms |
1128 KB |
Output is correct |
20 |
Correct |
319 ms |
10708 KB |
Output is correct |
21 |
Correct |
166 ms |
1140 KB |
Output is correct |
22 |
Correct |
216 ms |
888 KB |
Output is correct |
23 |
Correct |
461 ms |
27928 KB |
Output is correct |
24 |
Correct |
428 ms |
28604 KB |
Output is correct |
25 |
Correct |
769 ms |
56608 KB |
Output is correct |
26 |
Correct |
635 ms |
50712 KB |
Output is correct |
27 |
Correct |
174 ms |
1160 KB |
Output is correct |
28 |
Correct |
224 ms |
1044 KB |
Output is correct |
29 |
Correct |
304 ms |
1032 KB |
Output is correct |
30 |
Correct |
433 ms |
24420 KB |
Output is correct |
31 |
Correct |
171 ms |
1276 KB |
Output is correct |
32 |
Correct |
481 ms |
21312 KB |
Output is correct |
33 |
Correct |
225 ms |
1104 KB |
Output is correct |
34 |
Correct |
217 ms |
1164 KB |
Output is correct |
35 |
Correct |
263 ms |
1168 KB |
Output is correct |
36 |
Correct |
538 ms |
31864 KB |
Output is correct |
37 |
Correct |
552 ms |
30176 KB |
Output is correct |
38 |
Correct |
882 ms |
60568 KB |
Output is correct |
39 |
Correct |
708 ms |
59028 KB |
Output is correct |
40 |
Correct |
221 ms |
1248 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
421 ms |
1076 KB |
Output is correct |
2 |
Correct |
0 ms |
664 KB |
Output is correct |
3 |
Correct |
318 ms |
1084 KB |
Output is correct |
4 |
Correct |
456 ms |
10260 KB |
Output is correct |
5 |
Correct |
12 ms |
2100 KB |
Output is correct |
6 |
Correct |
362 ms |
3436 KB |
Output is correct |
7 |
Correct |
0 ms |
664 KB |
Output is correct |
8 |
Correct |
420 ms |
1124 KB |
Output is correct |
9 |
Correct |
376 ms |
1200 KB |
Output is correct |
10 |
Correct |
698 ms |
28040 KB |
Output is correct |
11 |
Correct |
703 ms |
29544 KB |
Output is correct |
12 |
Correct |
61 ms |
788 KB |
Output is correct |
13 |
Correct |
659 ms |
30876 KB |
Output is correct |
14 |
Correct |
333 ms |
1388 KB |
Output is correct |
15 |
Correct |
1 ms |
664 KB |
Output is correct |
16 |
Correct |
316 ms |
1068 KB |
Output is correct |
17 |
Correct |
410 ms |
1148 KB |
Output is correct |
18 |
Correct |
346 ms |
1148 KB |
Output is correct |
19 |
Correct |
317 ms |
1092 KB |
Output is correct |
20 |
Correct |
406 ms |
1152 KB |
Output is correct |
21 |
Correct |
364 ms |
1060 KB |
Output is correct |
22 |
Correct |
406 ms |
1056 KB |
Output is correct |
23 |
Correct |
418 ms |
1084 KB |
Output is correct |
24 |
Correct |
135 ms |
816 KB |
Output is correct |
25 |
Correct |
194 ms |
792 KB |
Output is correct |
26 |
Correct |
301 ms |
13448 KB |
Output is correct |
27 |
Correct |
144 ms |
844 KB |
Output is correct |
28 |
Correct |
210 ms |
10364 KB |
Output is correct |
29 |
Correct |
114 ms |
844 KB |
Output is correct |
30 |
Correct |
173 ms |
664 KB |
Output is correct |
31 |
Correct |
135 ms |
1108 KB |
Output is correct |
32 |
Correct |
375 ms |
25428 KB |
Output is correct |
33 |
Correct |
400 ms |
24504 KB |
Output is correct |
34 |
Correct |
599 ms |
48600 KB |
Output is correct |
35 |
Correct |
507 ms |
46316 KB |
Output is correct |
36 |
Correct |
163 ms |
1088 KB |
Output is correct |
37 |
Correct |
0 ms |
916 KB |
Output is correct |
38 |
Correct |
247 ms |
1020 KB |
Output is correct |
39 |
Correct |
158 ms |
1124 KB |
Output is correct |
40 |
Correct |
170 ms |
1124 KB |
Output is correct |
41 |
Correct |
282 ms |
10164 KB |
Output is correct |
42 |
Correct |
155 ms |
1128 KB |
Output is correct |
43 |
Correct |
319 ms |
10708 KB |
Output is correct |
44 |
Correct |
166 ms |
1140 KB |
Output is correct |
45 |
Correct |
216 ms |
888 KB |
Output is correct |
46 |
Correct |
461 ms |
27928 KB |
Output is correct |
47 |
Correct |
428 ms |
28604 KB |
Output is correct |
48 |
Correct |
769 ms |
56608 KB |
Output is correct |
49 |
Correct |
635 ms |
50712 KB |
Output is correct |
50 |
Correct |
174 ms |
1160 KB |
Output is correct |
51 |
Correct |
224 ms |
1044 KB |
Output is correct |
52 |
Correct |
304 ms |
1032 KB |
Output is correct |
53 |
Correct |
433 ms |
24420 KB |
Output is correct |
54 |
Correct |
171 ms |
1276 KB |
Output is correct |
55 |
Correct |
481 ms |
21312 KB |
Output is correct |
56 |
Correct |
225 ms |
1104 KB |
Output is correct |
57 |
Correct |
217 ms |
1164 KB |
Output is correct |
58 |
Correct |
263 ms |
1168 KB |
Output is correct |
59 |
Correct |
538 ms |
31864 KB |
Output is correct |
60 |
Correct |
552 ms |
30176 KB |
Output is correct |
61 |
Correct |
882 ms |
60568 KB |
Output is correct |
62 |
Correct |
708 ms |
59028 KB |
Output is correct |
63 |
Correct |
221 ms |
1248 KB |
Output is correct |
64 |
Correct |
352 ms |
1288 KB |
Output is correct |
65 |
Correct |
544 ms |
26528 KB |
Output is correct |
66 |
Correct |
594 ms |
23460 KB |
Output is correct |
67 |
Correct |
325 ms |
1460 KB |
Output is correct |
68 |
Correct |
305 ms |
1248 KB |
Output is correct |
69 |
Correct |
1032 ms |
59160 KB |
Output is correct |
70 |
Correct |
923 ms |
50760 KB |
Output is correct |
71 |
Correct |
338 ms |
7116 KB |
Output is correct |
72 |
Correct |
347 ms |
1792 KB |
Output is correct |