#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
namespace {
int n,m;
vector<ii> al[2005];
int w[2005];
priority_queue<ii,vector<ii>,greater<ii> > pq;
queue<int> q;
void send(int i,int k){
rep(bit,0,k){
if (i&(1<<bit)) SendA(1);
else SendA(0);
}
}
int get(int k){
int res=0;
rep(bit,0,k){
res|=q.front()<<bit;
q.pop();
}
return res;
}
bool flag=false;
int PREV=0;
int u,W,W_other;
void add(int i,int j){
//cout<<"debug A: "<<i<<" "<<j<<endl;
PREV=w[i]=j;
for (auto [it,w2]:al[i]){
pq.push({j+w2,it});
}
}
void proc(){
u=-1,W=1e18;
while (!pq.empty()){
tie(W,u)=pq.top();
if (w[u]!=-1){
u=-1,W=1e18;
pq.pop();
}
else break;
}
if (u==-1) send(511,9);
else send(W-PREV,9);
}
}
void InitA(signed N, signed A, std::vector<signed> U, std::vector<signed> V,
std::vector<signed> C) {
n=N,m=A;
rep(x,0,m){
al[U[x]].pub({V[x],C[x]});
al[V[x]].pub({U[x],C[x]});
}
memset(w,-1,sizeof(w));
add(0,0);
}
void ReceiveA(bool x){
q.push(x);
if (!flag){
if (sz(q)!=9) return;
proc();
W_other=get(9)+PREV;
if (W<=W_other){ //A wins
send(u,11);
add(u,W);
}
else{
flag=true;
}
}
else{
if (sz(q)!=11) return;
u=get(11);
add(u,W_other);
flag=false;
}
}
std::vector<signed> Answer() {
vector<signed> res;
rep(x,0,n) res.pub(w[x]);
return res;
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
namespace {
int n,m;
vector<ii> al[2005];
int w[2005];
priority_queue<ii,vector<ii>,greater<ii> > pq;
queue<int> q;
void send(int i,int k){
rep(bit,0,k){
if (i&(1<<bit)) SendB(1);
else SendB(0);
}
}
int get(int k){
int res=0;
rep(bit,0,k){
res|=q.front()<<bit;
q.pop();
}
return res;
}
bool flag=false;
int PREV=0;
int u,W,W_other;
void add(int i,int j){
//cout<<"debug B: "<<i<<" "<<j<<endl;
PREV=w[i]=j;
for (auto [it,w2]:al[i]){
pq.push({j+w2,it});
}
}
int count=0;
void proc(){
count++;
if (count==n) return;
u=-1,W=1e18;
while (!pq.empty()){
tie(W,u)=pq.top();
if (w[u]!=-1){
u=-1,W=1e18;
pq.pop();
}
else break;
}
if (u==-1) send(511,9);
else send(W-PREV,9);
}
};
void InitB(signed N, signed B, std::vector<signed> S, std::vector<signed> T,
std::vector<signed> D) {
n=N,m=B;
rep(x,0,m){
al[S[x]].pub({T[x],D[x]});
al[T[x]].pub({S[x],D[x]});
}
memset(w,-1,sizeof(w));
add(0,0);
proc();
}
void ReceiveB(bool y){
q.push(y);
if (!flag){
if (sz(q)!=9) return;
W_other=get(9)+PREV;
if (W<W_other){ //B wins
add(u,W);
send(u,11);
proc();
}
else{
flag=true;
}
}
else{
if (sz(q)!=11) return;
u=get(11);
add(u,W_other);
flag=false;
proc();
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
383 ms |
832 KB |
Output is correct |
2 |
Correct |
0 ms |
656 KB |
Output is correct |
3 |
Correct |
391 ms |
820 KB |
Output is correct |
4 |
Correct |
585 ms |
14484 KB |
Output is correct |
5 |
Correct |
28 ms |
1416 KB |
Output is correct |
6 |
Correct |
412 ms |
4060 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
672 KB |
Output is correct |
2 |
Correct |
400 ms |
752 KB |
Output is correct |
3 |
Correct |
455 ms |
860 KB |
Output is correct |
4 |
Correct |
698 ms |
40436 KB |
Output is correct |
5 |
Correct |
598 ms |
46976 KB |
Output is correct |
6 |
Correct |
99 ms |
780 KB |
Output is correct |
7 |
Correct |
586 ms |
47276 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
407 ms |
848 KB |
Output is correct |
2 |
Correct |
0 ms |
656 KB |
Output is correct |
3 |
Correct |
408 ms |
824 KB |
Output is correct |
4 |
Correct |
401 ms |
756 KB |
Output is correct |
5 |
Correct |
380 ms |
760 KB |
Output is correct |
6 |
Correct |
481 ms |
784 KB |
Output is correct |
7 |
Correct |
385 ms |
804 KB |
Output is correct |
8 |
Correct |
389 ms |
824 KB |
Output is correct |
9 |
Correct |
364 ms |
800 KB |
Output is correct |
10 |
Correct |
453 ms |
872 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
189 ms |
708 KB |
Output is correct |
2 |
Correct |
209 ms |
776 KB |
Output is correct |
3 |
Correct |
349 ms |
20812 KB |
Output is correct |
4 |
Correct |
206 ms |
656 KB |
Output is correct |
5 |
Correct |
293 ms |
14468 KB |
Output is correct |
6 |
Correct |
145 ms |
708 KB |
Output is correct |
7 |
Correct |
181 ms |
756 KB |
Output is correct |
8 |
Correct |
218 ms |
656 KB |
Output is correct |
9 |
Correct |
361 ms |
39840 KB |
Output is correct |
10 |
Correct |
347 ms |
39736 KB |
Output is correct |
11 |
Correct |
575 ms |
78816 KB |
Output is correct |
12 |
Correct |
493 ms |
74728 KB |
Output is correct |
13 |
Correct |
243 ms |
992 KB |
Output is correct |
14 |
Correct |
0 ms |
656 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
189 ms |
708 KB |
Output is correct |
2 |
Correct |
209 ms |
776 KB |
Output is correct |
3 |
Correct |
349 ms |
20812 KB |
Output is correct |
4 |
Correct |
206 ms |
656 KB |
Output is correct |
5 |
Correct |
293 ms |
14468 KB |
Output is correct |
6 |
Correct |
145 ms |
708 KB |
Output is correct |
7 |
Correct |
181 ms |
756 KB |
Output is correct |
8 |
Correct |
218 ms |
656 KB |
Output is correct |
9 |
Correct |
361 ms |
39840 KB |
Output is correct |
10 |
Correct |
347 ms |
39736 KB |
Output is correct |
11 |
Correct |
575 ms |
78816 KB |
Output is correct |
12 |
Correct |
493 ms |
74728 KB |
Output is correct |
13 |
Correct |
243 ms |
992 KB |
Output is correct |
14 |
Correct |
0 ms |
656 KB |
Output is correct |
15 |
Correct |
267 ms |
712 KB |
Output is correct |
16 |
Correct |
251 ms |
788 KB |
Output is correct |
17 |
Correct |
213 ms |
768 KB |
Output is correct |
18 |
Correct |
407 ms |
14720 KB |
Output is correct |
19 |
Correct |
225 ms |
892 KB |
Output is correct |
20 |
Correct |
408 ms |
14928 KB |
Output is correct |
21 |
Correct |
223 ms |
912 KB |
Output is correct |
22 |
Correct |
225 ms |
916 KB |
Output is correct |
23 |
Correct |
450 ms |
44344 KB |
Output is correct |
24 |
Correct |
463 ms |
44332 KB |
Output is correct |
25 |
Correct |
673 ms |
88148 KB |
Output is correct |
26 |
Correct |
518 ms |
82108 KB |
Output is correct |
27 |
Correct |
219 ms |
996 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
189 ms |
708 KB |
Output is correct |
2 |
Correct |
209 ms |
776 KB |
Output is correct |
3 |
Correct |
349 ms |
20812 KB |
Output is correct |
4 |
Correct |
206 ms |
656 KB |
Output is correct |
5 |
Correct |
293 ms |
14468 KB |
Output is correct |
6 |
Correct |
145 ms |
708 KB |
Output is correct |
7 |
Correct |
181 ms |
756 KB |
Output is correct |
8 |
Correct |
218 ms |
656 KB |
Output is correct |
9 |
Correct |
361 ms |
39840 KB |
Output is correct |
10 |
Correct |
347 ms |
39736 KB |
Output is correct |
11 |
Correct |
575 ms |
78816 KB |
Output is correct |
12 |
Correct |
493 ms |
74728 KB |
Output is correct |
13 |
Correct |
243 ms |
992 KB |
Output is correct |
14 |
Correct |
0 ms |
656 KB |
Output is correct |
15 |
Correct |
267 ms |
712 KB |
Output is correct |
16 |
Correct |
251 ms |
788 KB |
Output is correct |
17 |
Correct |
213 ms |
768 KB |
Output is correct |
18 |
Correct |
407 ms |
14720 KB |
Output is correct |
19 |
Correct |
225 ms |
892 KB |
Output is correct |
20 |
Correct |
408 ms |
14928 KB |
Output is correct |
21 |
Correct |
223 ms |
912 KB |
Output is correct |
22 |
Correct |
225 ms |
916 KB |
Output is correct |
23 |
Correct |
450 ms |
44344 KB |
Output is correct |
24 |
Correct |
463 ms |
44332 KB |
Output is correct |
25 |
Correct |
673 ms |
88148 KB |
Output is correct |
26 |
Correct |
518 ms |
82108 KB |
Output is correct |
27 |
Correct |
219 ms |
996 KB |
Output is correct |
28 |
Correct |
274 ms |
920 KB |
Output is correct |
29 |
Correct |
304 ms |
800 KB |
Output is correct |
30 |
Correct |
592 ms |
35968 KB |
Output is correct |
31 |
Correct |
292 ms |
796 KB |
Output is correct |
32 |
Correct |
537 ms |
32600 KB |
Output is correct |
33 |
Correct |
308 ms |
928 KB |
Output is correct |
34 |
Correct |
265 ms |
940 KB |
Output is correct |
35 |
Correct |
332 ms |
940 KB |
Output is correct |
36 |
Correct |
465 ms |
48892 KB |
Output is correct |
37 |
Correct |
445 ms |
49040 KB |
Output is correct |
38 |
Correct |
637 ms |
97208 KB |
Output is correct |
39 |
Correct |
655 ms |
91588 KB |
Output is correct |
40 |
Correct |
284 ms |
1452 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
383 ms |
832 KB |
Output is correct |
2 |
Correct |
0 ms |
656 KB |
Output is correct |
3 |
Correct |
391 ms |
820 KB |
Output is correct |
4 |
Correct |
585 ms |
14484 KB |
Output is correct |
5 |
Correct |
28 ms |
1416 KB |
Output is correct |
6 |
Correct |
412 ms |
4060 KB |
Output is correct |
7 |
Correct |
2 ms |
672 KB |
Output is correct |
8 |
Correct |
400 ms |
752 KB |
Output is correct |
9 |
Correct |
455 ms |
860 KB |
Output is correct |
10 |
Correct |
698 ms |
40436 KB |
Output is correct |
11 |
Correct |
598 ms |
46976 KB |
Output is correct |
12 |
Correct |
99 ms |
780 KB |
Output is correct |
13 |
Correct |
586 ms |
47276 KB |
Output is correct |
14 |
Correct |
407 ms |
848 KB |
Output is correct |
15 |
Correct |
0 ms |
656 KB |
Output is correct |
16 |
Correct |
408 ms |
824 KB |
Output is correct |
17 |
Correct |
401 ms |
756 KB |
Output is correct |
18 |
Correct |
380 ms |
760 KB |
Output is correct |
19 |
Correct |
481 ms |
784 KB |
Output is correct |
20 |
Correct |
385 ms |
804 KB |
Output is correct |
21 |
Correct |
389 ms |
824 KB |
Output is correct |
22 |
Correct |
364 ms |
800 KB |
Output is correct |
23 |
Correct |
453 ms |
872 KB |
Output is correct |
24 |
Correct |
189 ms |
708 KB |
Output is correct |
25 |
Correct |
209 ms |
776 KB |
Output is correct |
26 |
Correct |
349 ms |
20812 KB |
Output is correct |
27 |
Correct |
206 ms |
656 KB |
Output is correct |
28 |
Correct |
293 ms |
14468 KB |
Output is correct |
29 |
Correct |
145 ms |
708 KB |
Output is correct |
30 |
Correct |
181 ms |
756 KB |
Output is correct |
31 |
Correct |
218 ms |
656 KB |
Output is correct |
32 |
Correct |
361 ms |
39840 KB |
Output is correct |
33 |
Correct |
347 ms |
39736 KB |
Output is correct |
34 |
Correct |
575 ms |
78816 KB |
Output is correct |
35 |
Correct |
493 ms |
74728 KB |
Output is correct |
36 |
Correct |
243 ms |
992 KB |
Output is correct |
37 |
Correct |
0 ms |
656 KB |
Output is correct |
38 |
Correct |
267 ms |
712 KB |
Output is correct |
39 |
Correct |
251 ms |
788 KB |
Output is correct |
40 |
Correct |
213 ms |
768 KB |
Output is correct |
41 |
Correct |
407 ms |
14720 KB |
Output is correct |
42 |
Correct |
225 ms |
892 KB |
Output is correct |
43 |
Correct |
408 ms |
14928 KB |
Output is correct |
44 |
Correct |
223 ms |
912 KB |
Output is correct |
45 |
Correct |
225 ms |
916 KB |
Output is correct |
46 |
Correct |
450 ms |
44344 KB |
Output is correct |
47 |
Correct |
463 ms |
44332 KB |
Output is correct |
48 |
Correct |
673 ms |
88148 KB |
Output is correct |
49 |
Correct |
518 ms |
82108 KB |
Output is correct |
50 |
Correct |
219 ms |
996 KB |
Output is correct |
51 |
Correct |
274 ms |
920 KB |
Output is correct |
52 |
Correct |
304 ms |
800 KB |
Output is correct |
53 |
Correct |
592 ms |
35968 KB |
Output is correct |
54 |
Correct |
292 ms |
796 KB |
Output is correct |
55 |
Correct |
537 ms |
32600 KB |
Output is correct |
56 |
Correct |
308 ms |
928 KB |
Output is correct |
57 |
Correct |
265 ms |
940 KB |
Output is correct |
58 |
Correct |
332 ms |
940 KB |
Output is correct |
59 |
Correct |
465 ms |
48892 KB |
Output is correct |
60 |
Correct |
445 ms |
49040 KB |
Output is correct |
61 |
Correct |
637 ms |
97208 KB |
Output is correct |
62 |
Correct |
655 ms |
91588 KB |
Output is correct |
63 |
Correct |
284 ms |
1452 KB |
Output is correct |
64 |
Correct |
339 ms |
1024 KB |
Output is correct |
65 |
Correct |
761 ms |
40768 KB |
Output is correct |
66 |
Correct |
694 ms |
34720 KB |
Output is correct |
67 |
Correct |
410 ms |
988 KB |
Output is correct |
68 |
Correct |
332 ms |
988 KB |
Output is correct |
69 |
Correct |
842 ms |
93396 KB |
Output is correct |
70 |
Correct |
804 ms |
83376 KB |
Output is correct |
71 |
Correct |
380 ms |
10992 KB |
Output is correct |
72 |
Correct |
370 ms |
1828 KB |
Output is correct |