#include <bits/stdc++.h>
#include "Azer.h"
using namespace std;
namespace{
const int MAXN = 99999999;
int suma = 0;
pair <int,int> akt_top;
int akt = 0;
int akt_2 = 0;
int akt_bits = 9;
string akt_str = "";
vector<int> answer={0};
int info[2];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
vector<vector<pair<int,int>>> graf(500000);
string decToBinary(int n,int bits)
{
string ans = "";
for (int i = bits; i >= 0; i--) {
int k = n >> i;
if (k & 1)
ans += "1";
else
ans += "0";
}
return ans;
}
int binaryToDecimal(string str)
{
int dec_num = 0;
int power = 0 ;
int n = str.length() ;
for(int i = n-1 ; i>=0 ; i--){
if(str[i] == '1'){
dec_num += (1<<power) ;
}
power++ ;
}
return dec_num;
}
void send(int a,int bits){
bits--;
string bin = decToBinary(a,bits);
//cout << "WYSYLA A: " << a << " z tyloma bitami: " << bits << " " << bin << endl;
for (int i=0; i<bits+1; i++){
SendA(bin[i]-'0');
}
}
}
void ReceiveA(bool x){
if (x == 0) akt_str += "0";
else akt_str += "1";
if (akt_2==akt_bits-1){
int liczba = binaryToDecimal(akt_str);
//cout << "otrzymal A: " << liczba << " akt bity: " << akt_bits << " str "<< akt_str <<endl;
if (akt==0){ // wartosc
info[0] = liczba;
while (pq.top().first != MAXN && answer[pq.top().second] <= pq.top().first) {
pq.pop();
}
if (pq.empty()) pq.push({MAXN,2024});
akt_top = pq.top();
if (min(akt_top.first-suma,507)==507 && info[0]==507) return;
send(min(akt_top.first-suma,507),9);
if (akt_top.first-suma < info[0]){
suma = akt_top.first;
send(akt_top.second,11);
pq.pop();
answer[akt_top.second] = akt_top.first;
//cout << "A WYBRANY: " << akt_top.first<<endl;
//// DIJKSTRA
for (auto [a,val] : graf[akt_top.second]){
if (answer[a] > akt_top.first+val){
pq.push({akt_top.first+val,a});
}
}
//for (auto i : answer) cout << i << " ";
// cout << endl;
akt_bits = 9;
}
else{
akt = 1;
akt_bits = 11;
}
}
else if(akt==1){ // Wierzcholek
info[1] = liczba;
suma += info[0];
answer[info[1]] = suma;
//cout << "A WYBRANY: " << info[0]<<endl;
for (auto [a,val] : graf[info[1]]){
if (answer[a] > suma+val){
pq.push({suma+val,a});
}
}
//for (auto i : answer) cout << i << " ";
//cout << endl;
akt = 0;
akt_bits = 9;
}
akt_2 = 0;
akt_str = "";
}
else akt_2 += 1;
}
void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C){
for (int i=1; i<N; i++){
answer.push_back(9999999);
}
for (int i=0; i<A; i++){
graf[U[i]].push_back({V[i],C[i]});
graf[V[i]].push_back({U[i],C[i]});
}
for (auto [a,val] : graf[0]){
pq.push({val,a});
}
pq.push({MAXN,2024});
}
vector<int> Answer(){
return answer;
}
#include <bits/stdc++.h>
#include "Baijan.h"
using namespace std;
namespace{
int n;
int liczba_odw = 0;
const int MAXN = 99999999;
int suma = 0;
pair <int,int> akt_top;
int akt = 0,akt_2=0,akt_bits=9;
int info[2];
string akt_str="";
vector<int> answer={0};
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
vector<vector<pair<int,int>>> graf(500000);
string decToBinary(int n,int bits)
{
string ans = "";
for (int i = bits; i >= 0; i--) {
int k = n >> i;
if (k & 1)
ans += "1";
else
ans += "0";
}
return ans;
}
int binaryToDecimal(string str)
{
int dec_num = 0;
int power = 0 ;
int n = str.length() ;
for(int i = n-1 ; i>=0 ; i--){
if(str[i] == '1'){
dec_num += (1<<power) ;
}
power++ ;
}
return dec_num;
}
void send(int a,int bits){
bits--;
string bin = decToBinary(a,bits);
//cout << "WYSYLA B: " << a << " z tyloma bitami: " << bits << " " << bin << endl;
for (int i=0; i<bits+1; i++){
SendB(bin[i]-'0');
}
}
}
void ReceiveB(bool y){
if (y == 0) akt_str += "0";
else akt_str += "1";
//cout << akt_bits << " " << akt_2 <<endl;
if (akt_2==akt_bits-1){
int liczba = binaryToDecimal(akt_str);
//cout << "otrzymal B: " << liczba << " akt bity: " << akt_bits << " str "<< akt_str <<endl;
if (akt==0){ // wartosc
info[0] = liczba;
//cout << "TEST" << endl;
while (pq.top().first != MAXN && answer[pq.top().second] <= pq.top().first) pq.pop();
if (pq.empty()) pq.push({MAXN,2024});
akt_top = pq.top();
if (min(akt_top.first-suma,507)==507 && info[0]==507) return;
//send(akt_top.first,9);
if (akt_top.first-suma <= info[0]){
liczba_odw ++;
suma = akt_top.first;
send(akt_top.second,11);
pq.pop();
answer[akt_top.second] = akt_top.first;
//cout << "B WYBRANY: " << akt_top.first << " " << akt_top.second <<endl;
//// DIJKSTRA
//cout << " TETS";
for (auto [a,val] : graf[akt_top.second]){
//cout << answer[a] << " " << a << " " << akt_top.first << endl;
if (answer[a] > akt_top.first+val){
pq.push({akt_top.first+val,a});
}
}
akt_bits = 9;
//cout << " TETS2";
//cout << pq.top().first << endl;
while (pq.top().first != MAXN && answer[pq.top().second] <= pq.top().first) {
//cout << pq.top().first << " " << pq.top().second << endl;
pq.pop();
}
//cout << "DWD";
//for (auto i : answer) cout << i << " ";
//cout << endl;
if (pq.empty()) pq.push({MAXN,2024});
//cout << "DW";
if (liczba_odw==n) return;
send(min(pq.top().first-suma,507),9);
//cout << " TETS";
}
else{
akt = 1;
akt_bits = 11;
}
}
else if(akt==1){ // Wierzcholek
liczba_odw ++;
info[1] = liczba;
suma += info[0];
answer[info[1]] = suma;
//cout << "B WYBRANY: " << info[0]<<endl;
for (auto [a,val] : graf[info[1]]){
//cout << answer[a] << " " << a << " " << info[0] << endl;
if (answer[a] > suma+val){
pq.push({suma+val,a});
}
}
//for (auto i : answer) cout << i << " ";
//cout << endl;
akt = 0;
akt_bits = 9;
while (pq.top().first != MAXN && answer[pq.top().second] <= pq.top().first) pq.pop();
if (pq.empty()) pq.push({MAXN,2024});
if (liczba_odw==n) return;
send(min(pq.top().first-suma,507),9);
}
akt_2 = 0;
akt_str = "";
//cout << "TEST#";
}
else akt_2 += 1;
}
void SendB(bool x);
void InitB(int N, int B, std::vector<int> S, std::vector<int> T, std::vector<int> D){
n = N;
for (int i=1; i<N; i++){
answer.push_back(9999999);
}
for (int i=0; i<B; i++){
graf[S[i]].push_back({T[i],D[i]});
graf[T[i]].push_back({S[i],D[i]});
}
for (auto [a,val] : graf[0]){
pq.push({val,a});
}
pq.push({MAXN,2024});
liczba_odw ++;
send(min(pq.top().first,507),9);
//cout << "ELO" <<endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
369 ms |
24544 KB |
Output is correct |
2 |
Correct |
8 ms |
24216 KB |
Output is correct |
3 |
Correct |
296 ms |
24288 KB |
Output is correct |
4 |
Correct |
451 ms |
33768 KB |
Output is correct |
5 |
Correct |
25 ms |
24564 KB |
Output is correct |
6 |
Correct |
387 ms |
26796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
24216 KB |
Output is correct |
2 |
Correct |
368 ms |
24364 KB |
Output is correct |
3 |
Correct |
372 ms |
24428 KB |
Output is correct |
4 |
Correct |
481 ms |
51448 KB |
Output is correct |
5 |
Correct |
499 ms |
50664 KB |
Output is correct |
6 |
Correct |
57 ms |
24336 KB |
Output is correct |
7 |
Correct |
532 ms |
49140 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
369 ms |
24348 KB |
Output is correct |
2 |
Correct |
7 ms |
24216 KB |
Output is correct |
3 |
Correct |
395 ms |
24288 KB |
Output is correct |
4 |
Correct |
332 ms |
24360 KB |
Output is correct |
5 |
Correct |
343 ms |
24364 KB |
Output is correct |
6 |
Correct |
335 ms |
24352 KB |
Output is correct |
7 |
Correct |
392 ms |
24360 KB |
Output is correct |
8 |
Correct |
351 ms |
24292 KB |
Output is correct |
9 |
Correct |
343 ms |
24288 KB |
Output is correct |
10 |
Correct |
393 ms |
24500 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
159 ms |
24480 KB |
Output is correct |
2 |
Correct |
143 ms |
24280 KB |
Output is correct |
3 |
Correct |
211 ms |
37224 KB |
Output is correct |
4 |
Correct |
196 ms |
24216 KB |
Output is correct |
5 |
Correct |
229 ms |
33796 KB |
Output is correct |
6 |
Correct |
162 ms |
24216 KB |
Output is correct |
7 |
Correct |
197 ms |
24216 KB |
Output is correct |
8 |
Correct |
147 ms |
24216 KB |
Output is correct |
9 |
Correct |
265 ms |
45252 KB |
Output is correct |
10 |
Correct |
347 ms |
44224 KB |
Output is correct |
11 |
Correct |
403 ms |
65180 KB |
Output is correct |
12 |
Correct |
435 ms |
63028 KB |
Output is correct |
13 |
Correct |
150 ms |
24216 KB |
Output is correct |
14 |
Correct |
10 ms |
24216 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
159 ms |
24480 KB |
Output is correct |
2 |
Correct |
143 ms |
24280 KB |
Output is correct |
3 |
Correct |
211 ms |
37224 KB |
Output is correct |
4 |
Correct |
196 ms |
24216 KB |
Output is correct |
5 |
Correct |
229 ms |
33796 KB |
Output is correct |
6 |
Correct |
162 ms |
24216 KB |
Output is correct |
7 |
Correct |
197 ms |
24216 KB |
Output is correct |
8 |
Correct |
147 ms |
24216 KB |
Output is correct |
9 |
Correct |
265 ms |
45252 KB |
Output is correct |
10 |
Correct |
347 ms |
44224 KB |
Output is correct |
11 |
Correct |
403 ms |
65180 KB |
Output is correct |
12 |
Correct |
435 ms |
63028 KB |
Output is correct |
13 |
Correct |
150 ms |
24216 KB |
Output is correct |
14 |
Correct |
10 ms |
24216 KB |
Output is correct |
15 |
Correct |
224 ms |
24216 KB |
Output is correct |
16 |
Correct |
209 ms |
24216 KB |
Output is correct |
17 |
Correct |
213 ms |
24216 KB |
Output is correct |
18 |
Correct |
266 ms |
34016 KB |
Output is correct |
19 |
Correct |
186 ms |
24216 KB |
Output is correct |
20 |
Correct |
277 ms |
34136 KB |
Output is correct |
21 |
Correct |
188 ms |
24216 KB |
Output is correct |
22 |
Correct |
204 ms |
24440 KB |
Output is correct |
23 |
Correct |
253 ms |
48384 KB |
Output is correct |
24 |
Correct |
364 ms |
47972 KB |
Output is correct |
25 |
Correct |
548 ms |
70868 KB |
Output is correct |
26 |
Correct |
419 ms |
66176 KB |
Output is correct |
27 |
Correct |
156 ms |
24556 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
159 ms |
24480 KB |
Output is correct |
2 |
Correct |
143 ms |
24280 KB |
Output is correct |
3 |
Correct |
211 ms |
37224 KB |
Output is correct |
4 |
Correct |
196 ms |
24216 KB |
Output is correct |
5 |
Correct |
229 ms |
33796 KB |
Output is correct |
6 |
Correct |
162 ms |
24216 KB |
Output is correct |
7 |
Correct |
197 ms |
24216 KB |
Output is correct |
8 |
Correct |
147 ms |
24216 KB |
Output is correct |
9 |
Correct |
265 ms |
45252 KB |
Output is correct |
10 |
Correct |
347 ms |
44224 KB |
Output is correct |
11 |
Correct |
403 ms |
65180 KB |
Output is correct |
12 |
Correct |
435 ms |
63028 KB |
Output is correct |
13 |
Correct |
150 ms |
24216 KB |
Output is correct |
14 |
Correct |
10 ms |
24216 KB |
Output is correct |
15 |
Correct |
224 ms |
24216 KB |
Output is correct |
16 |
Correct |
209 ms |
24216 KB |
Output is correct |
17 |
Correct |
213 ms |
24216 KB |
Output is correct |
18 |
Correct |
266 ms |
34016 KB |
Output is correct |
19 |
Correct |
186 ms |
24216 KB |
Output is correct |
20 |
Correct |
277 ms |
34136 KB |
Output is correct |
21 |
Correct |
188 ms |
24216 KB |
Output is correct |
22 |
Correct |
204 ms |
24440 KB |
Output is correct |
23 |
Correct |
253 ms |
48384 KB |
Output is correct |
24 |
Correct |
364 ms |
47972 KB |
Output is correct |
25 |
Correct |
548 ms |
70868 KB |
Output is correct |
26 |
Correct |
419 ms |
66176 KB |
Output is correct |
27 |
Correct |
156 ms |
24556 KB |
Output is correct |
28 |
Correct |
275 ms |
24216 KB |
Output is correct |
29 |
Correct |
269 ms |
24288 KB |
Output is correct |
30 |
Correct |
429 ms |
47560 KB |
Output is correct |
31 |
Correct |
230 ms |
24280 KB |
Output is correct |
32 |
Correct |
338 ms |
44992 KB |
Output is correct |
33 |
Correct |
300 ms |
24356 KB |
Output is correct |
34 |
Correct |
247 ms |
24388 KB |
Output is correct |
35 |
Correct |
214 ms |
24392 KB |
Output is correct |
36 |
Correct |
345 ms |
49616 KB |
Output is correct |
37 |
Correct |
494 ms |
49484 KB |
Output is correct |
38 |
Correct |
586 ms |
76352 KB |
Output is correct |
39 |
Correct |
588 ms |
74368 KB |
Output is correct |
40 |
Correct |
253 ms |
24628 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
369 ms |
24544 KB |
Output is correct |
2 |
Correct |
8 ms |
24216 KB |
Output is correct |
3 |
Correct |
296 ms |
24288 KB |
Output is correct |
4 |
Correct |
451 ms |
33768 KB |
Output is correct |
5 |
Correct |
25 ms |
24564 KB |
Output is correct |
6 |
Correct |
387 ms |
26796 KB |
Output is correct |
7 |
Correct |
8 ms |
24216 KB |
Output is correct |
8 |
Correct |
368 ms |
24364 KB |
Output is correct |
9 |
Correct |
372 ms |
24428 KB |
Output is correct |
10 |
Correct |
481 ms |
51448 KB |
Output is correct |
11 |
Correct |
499 ms |
50664 KB |
Output is correct |
12 |
Correct |
57 ms |
24336 KB |
Output is correct |
13 |
Correct |
532 ms |
49140 KB |
Output is correct |
14 |
Correct |
369 ms |
24348 KB |
Output is correct |
15 |
Correct |
7 ms |
24216 KB |
Output is correct |
16 |
Correct |
395 ms |
24288 KB |
Output is correct |
17 |
Correct |
332 ms |
24360 KB |
Output is correct |
18 |
Correct |
343 ms |
24364 KB |
Output is correct |
19 |
Correct |
335 ms |
24352 KB |
Output is correct |
20 |
Correct |
392 ms |
24360 KB |
Output is correct |
21 |
Correct |
351 ms |
24292 KB |
Output is correct |
22 |
Correct |
343 ms |
24288 KB |
Output is correct |
23 |
Correct |
393 ms |
24500 KB |
Output is correct |
24 |
Correct |
159 ms |
24480 KB |
Output is correct |
25 |
Correct |
143 ms |
24280 KB |
Output is correct |
26 |
Correct |
211 ms |
37224 KB |
Output is correct |
27 |
Correct |
196 ms |
24216 KB |
Output is correct |
28 |
Correct |
229 ms |
33796 KB |
Output is correct |
29 |
Correct |
162 ms |
24216 KB |
Output is correct |
30 |
Correct |
197 ms |
24216 KB |
Output is correct |
31 |
Correct |
147 ms |
24216 KB |
Output is correct |
32 |
Correct |
265 ms |
45252 KB |
Output is correct |
33 |
Correct |
347 ms |
44224 KB |
Output is correct |
34 |
Correct |
403 ms |
65180 KB |
Output is correct |
35 |
Correct |
435 ms |
63028 KB |
Output is correct |
36 |
Correct |
150 ms |
24216 KB |
Output is correct |
37 |
Correct |
10 ms |
24216 KB |
Output is correct |
38 |
Correct |
224 ms |
24216 KB |
Output is correct |
39 |
Correct |
209 ms |
24216 KB |
Output is correct |
40 |
Correct |
213 ms |
24216 KB |
Output is correct |
41 |
Correct |
266 ms |
34016 KB |
Output is correct |
42 |
Correct |
186 ms |
24216 KB |
Output is correct |
43 |
Correct |
277 ms |
34136 KB |
Output is correct |
44 |
Correct |
188 ms |
24216 KB |
Output is correct |
45 |
Correct |
204 ms |
24440 KB |
Output is correct |
46 |
Correct |
253 ms |
48384 KB |
Output is correct |
47 |
Correct |
364 ms |
47972 KB |
Output is correct |
48 |
Correct |
548 ms |
70868 KB |
Output is correct |
49 |
Correct |
419 ms |
66176 KB |
Output is correct |
50 |
Correct |
156 ms |
24556 KB |
Output is correct |
51 |
Correct |
275 ms |
24216 KB |
Output is correct |
52 |
Correct |
269 ms |
24288 KB |
Output is correct |
53 |
Correct |
429 ms |
47560 KB |
Output is correct |
54 |
Correct |
230 ms |
24280 KB |
Output is correct |
55 |
Correct |
338 ms |
44992 KB |
Output is correct |
56 |
Correct |
300 ms |
24356 KB |
Output is correct |
57 |
Correct |
247 ms |
24388 KB |
Output is correct |
58 |
Correct |
214 ms |
24392 KB |
Output is correct |
59 |
Correct |
345 ms |
49616 KB |
Output is correct |
60 |
Correct |
494 ms |
49484 KB |
Output is correct |
61 |
Correct |
586 ms |
76352 KB |
Output is correct |
62 |
Correct |
588 ms |
74368 KB |
Output is correct |
63 |
Correct |
253 ms |
24628 KB |
Output is correct |
64 |
Correct |
329 ms |
24704 KB |
Output is correct |
65 |
Correct |
554 ms |
50180 KB |
Output is correct |
66 |
Correct |
591 ms |
46880 KB |
Output is correct |
67 |
Correct |
352 ms |
24428 KB |
Output is correct |
68 |
Correct |
379 ms |
24564 KB |
Output is correct |
69 |
Correct |
673 ms |
75376 KB |
Output is correct |
70 |
Correct |
720 ms |
66640 KB |
Output is correct |
71 |
Correct |
357 ms |
29708 KB |
Output is correct |
72 |
Correct |
373 ms |
25164 KB |
Output is correct |