This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "Anna.h"
#include<bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define ll long long
//#define int ll
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
//#define inf 1010000000
#define inf 4000000000000000000
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 826
#endif
namespace {
int n,l,r,res;
int zck;
const int K=201;
vector<int> vec1,vec2;
vector<bool> tree1,tree2,tree3;
bool flag;
vector<int> build(vector<bool>& tree){
vector<int> stk;
vector<int> pre;
int cur=0;
for(auto i: tree){
if(i){
pre.pb(sz(stk)?stk.back():-1);
if(pre.back()==-1) bug(cur);
stk.pb(cur);
cur++;
}
else{
stk.pop_back();
}
}
return pre;
}
void response(vector<int> id, vector<int> pre, vector<int>& vec){
int L,R;
rep(sz(id)) if(id[i]>=l){
L=i;
break;
}
rep3(i,sz(id)-1,0) if(id[i]<=r){
R=i;
break;
}
bug(L,R);
vector<int> tmp1;
rep(K) tmp1.pb(sz(id)/K);
rep(sz(id)%K) tmp1[i]++;
int lpos,rpos,cur=0,y;
rep(K){
if(tmp1[i]+cur>L){
lpos=i;
break;
}
cur+=tmp1[i];
}
cur=0;
rep(K){
if(tmp1[i]+cur>R){
rpos=i;
break;
}
cur+=tmp1[i];
}
if(rpos<=lpos+1){
SendA(0);
flag=0;
int z=lpos;
rep(8) SendA(z&1),z>>=1;
cur=0;
rep(lpos) cur+=tmp1[i];
rep(tmp1[lpos]) vec.pb(id[cur+i]);
if(lpos+1<sz(tmp1)) rep(tmp1[lpos+1]) vec.pb(id[cur+tmp1[lpos]+i]);
//for(auto i: vec) bug(i);
return;
}
rep2(i,lpos+1,rpos) if(pre[i]<lpos+1) y=i;
SendA(1);
flag=1;
int z=y;
rep(8) SendA(z&1),z>>=1;
cur=0;
rep(pre[y]) cur+=tmp1[i];
if(pre[y]>=0) rep(tmp1[pre[y]]) vec.pb(id[cur+i]);
bug(pre[y],y);
bug("A",sz(vec));
vec.pb(-1);
rep2(i,y+1,sz(pre)) if(pre[i]<y){
bug(i);
cur=0;
rep1(j,i) cur+=tmp1[j];
rep1(j,tmp1[i]) vec.pb(id[cur+j]);
break;
}
bug("A",sz(vec));
//for(auto i: vec) bug(i);
}
} // namespace
void InitA(int N, int L, int R) {
n=N,l=L,r=R,zck=0;
}
void ReceiveA(bool x) {
if(!zck){
static int cnt=2*K;
tree1.pb(x);
cnt--;
if(cnt<=0){
vector<int> tmp;
rep(n) tmp.pb(i);
vector<int> pre=build(tree1);
response(tmp,pre,vec1);
zck++;
}
}
else if(zck==1){
if(flag){
static int cnt=20,pos=0;
pos+=x*(1<<(20-cnt));
cnt--;
if(!cnt){
for(auto& i: vec1) if(i==-1) i=pos;
flag=0;
}
}
else{
static int cnt=2*K;
tree2.pb(x);
cnt--;
if(cnt<=0){
vector<int> pre=build(tree2);
response(vec1,pre,vec2);
bug(sz(vec1),sz(vec2));
zck++;
}
}
}
else{
if(flag){
static int cnt=20,pos=0;
pos+=x*(1<<(20-cnt));
cnt--;
if(!cnt){
for(auto& i: vec2) if(i==-1) i=pos;
flag=0;
}
}
else{
static int cnt=2*sz(vec2);
tree3.pb(x);
cnt--;
if(cnt<=0){
vector<int> pre=build(tree3);
rep3(i,sz(vec2)-1,0) if(vec2[i]<=r&&(pre[i]==-1||vec2[pre[i]]<l)){
res=vec2[i];
bug(vec2[i],r,pre[i],vec2[pre[i]]);
break;
}
}
}
}
}
int Answer() {
bug(res,sz(vec1),sz(vec2));
bool b=0;
for(auto i: vec2) bug(i);
return res;
}
#include "Bruno.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
//#define int ll
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define inf 1010000000
//#define inf 4000000000000000000
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#ifdef i_am_noob
#define bug(...) cerr << "#🉐️" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 826
#endif
namespace {
int n;
int zck,orzck;
bool flag;
vector<int> a,vec1,vec2,minvec;
const int K=201;
vector<bool> build(vector<int>& vec){
vector<bool> res;
vector<int> stk;
for(auto i: vec){
while(sz(stk)&&i<stk.back()) res.pb(0),stk.pop_back();
if(stk.empty()) bug(i);
res.pb(1),stk.pb(i);
}
rep(sz(stk)) res.pb(0);
assert(sz(res)==2*sz(vec));
return res;
}
vector<int> Get(vector<int>& id, int val){
vector<int> tmp1;
rep(K) tmp1.pb(sz(id)/K);
rep(sz(id)%K) tmp1[i]++;
int cur;
vector<int> res;
if(sz(id)<100) for(auto i: id) bug(i);
if(flag){
bug(sz(id));
cur=0;
rep(val) cur+=tmp1[i];
int minn=n+1,minid;
rep2(i,cur,cur+tmp1[val]) if(a[id[i]]<minn) minn=a[id[i]],minid=id[i];
int z=minid;
rep(20) SendB(z&1),z>>=1;
rep3(i,val-1,0) if(minvec[i]<minvec[val]){
cur=0;
rep1(j,i) cur+=tmp1[j];
rep2(j,cur,cur+tmp1[i]) res.pb(id[j]);
bug(i);
break;
}
bug("B",sz(res));
res.pb(minid);
bug(val);
rep2(i,val+1,sz(minvec)) if(minvec[i]<minvec[val]){
bug(i);
cur=0;
rep1(j,i) cur+=tmp1[j];
rep2(j,cur,cur+tmp1[i]) res.pb(id[j]);
break;
}
bug("B",sz(res));
}
else{
cur=0;
rep(val) cur+=tmp1[i];
rep2(i,cur,cur+tmp1[val]) res.pb(id[i]);
if(val+1<sz(tmp1)) rep2(i,cur+tmp1[val],cur+tmp1[val]+tmp1[val+1]) res.pb(id[i]);
}
//for(auto i: res) bug(i);
return res;
}
vector<bool> tree1,tree2,tree3;
} // namespace
void InitB(int N, vector<int> A) {
n=N,a=A,zck=0;
vector<int> tmp1;
rep(K) tmp1.pb(n/K);
rep(n%K) tmp1[i]++;
int cur=0;
rep(K){
int minn=inf;
rep2(j,cur,cur+tmp1[i]) minn=min(minn,a[j]);
minvec.pb(minn);
cur+=tmp1[i];
}
tree1=build(minvec);
bug(sz(tree1));
for(auto i: tree1) SendB(i),orzck++;
}
void ReceiveB(bool y) {
if(!zck){
flag=y;
zck++;
}
else if(zck==1){
static int cnt=8,val=0;
val+=y*(1<<(8-cnt));
cnt--;
if(!cnt){
vector<int> tmp,tmp1;
rep(n) tmp.pb(i);
vec1=Get(tmp,val);
rep(K) tmp1.pb(sz(vec1)/K);
rep(sz(vec1)%K) tmp1[i]++;
minvec.clear();
int cur=0;
rep(K){
int minn=inf;
rep2(j,cur,cur+tmp1[i]) minn=min(minn,a[vec1[j]]);
minvec.pb(minn);
cur+=tmp1[i];
}
tree2=build(minvec);
bug(sz(tree2));
for(auto i: tree2) SendB(i),orzck++;
zck++;
}
}
else if(zck==2){
flag=y;
zck++;
}
else{
static int cnt=8,val=0;
val+=y*(1<<(8-cnt));
cnt--;
if(!cnt){
vec2=Get(vec1,val);
minvec.clear();
for(auto i: vec2) minvec.pb(a[i]),bug(i,a[i]);
tree2=build(minvec);
bug(sz(tree2),sz(vec1),sz(vec2));
for(auto i: tree2) SendB(i),orzck++;
zck++;
assert(orzck<=300);
}
}
}
Compilation message (stderr)
Anna.cpp: In function 'std::vector<int> {anonymous}::build(std::vector<bool>&)':
Anna.cpp:26:18: warning: statement has no effect [-Wunused-value]
26 | #define bug(...) 826
| ^~~
Anna.cpp:45:32: note: in expansion of macro 'bug'
45 | if(pre.back()==-1) bug(cur);
| ^~~
Anna.cpp: In function 'void {anonymous}::response(std::vector<int>, std::vector<int>, std::vector<int>&)':
Anna.cpp:26:18: warning: statement has no effect [-Wunused-value]
26 | #define bug(...) 826
| ^~~
Anna.cpp:66:5: note: in expansion of macro 'bug'
66 | bug(L,R);
| ^~~
Anna.cpp:26:18: warning: statement has no effect [-Wunused-value]
26 | #define bug(...) 826
| ^~~
Anna.cpp:106:5: note: in expansion of macro 'bug'
106 | bug(pre[y],y);
| ^~~
Anna.cpp:26:18: warning: statement has no effect [-Wunused-value]
26 | #define bug(...) 826
| ^~~
Anna.cpp:107:5: note: in expansion of macro 'bug'
107 | bug("A",sz(vec));
| ^~~
Anna.cpp:26:18: warning: statement has no effect [-Wunused-value]
26 | #define bug(...) 826
| ^~~
Anna.cpp:110:9: note: in expansion of macro 'bug'
110 | bug(i);
| ^~~
Anna.cpp:26:18: warning: statement has no effect [-Wunused-value]
26 | #define bug(...) 826
| ^~~
Anna.cpp:116:5: note: in expansion of macro 'bug'
116 | bug("A",sz(vec));
| ^~~
Anna.cpp: In function 'void ReceiveA(bool)':
Anna.cpp:26:18: warning: statement has no effect [-Wunused-value]
26 | #define bug(...) 826
| ^~~
Anna.cpp:156:17: note: in expansion of macro 'bug'
156 | bug(sz(vec1),sz(vec2));
| ^~~
Anna.cpp:26:18: warning: statement has no effect [-Wunused-value]
26 | #define bug(...) 826
| ^~~
Anna.cpp:179:21: note: in expansion of macro 'bug'
179 | bug(vec2[i],r,pre[i],vec2[pre[i]]);
| ^~~
Anna.cpp: In function 'int Answer()':
Anna.cpp:26:18: warning: statement has no effect [-Wunused-value]
26 | #define bug(...) 826
| ^~~
Anna.cpp:188:5: note: in expansion of macro 'bug'
188 | bug(res,sz(vec1),sz(vec2));
| ^~~
Anna.cpp:26:18: warning: statement has no effect [-Wunused-value]
26 | #define bug(...) 826
| ^~~
Anna.cpp:190:23: note: in expansion of macro 'bug'
190 | for(auto i: vec2) bug(i);
| ^~~
Anna.cpp:190:14: warning: unused variable 'i' [-Wunused-variable]
190 | for(auto i: vec2) bug(i);
| ^
Anna.cpp:189:10: warning: unused variable 'b' [-Wunused-variable]
189 | bool b=0;
| ^
Anna.cpp: In function 'void {anonymous}::response(std::vector<int>, std::vector<int>, std::vector<int>&)':
Anna.cpp:70:9: warning: 'lpos' may be used uninitialized in this function [-Wmaybe-uninitialized]
70 | int lpos,rpos,cur=0,y;
| ^~~~
Anna.cpp:109:25: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
109 | rep2(i,y+1,sz(pre)) if(pre[i]<y){
| ^~
Anna.cpp:12:37: warning: 'rpos' may be used uninitialized in this function [-Wmaybe-uninitialized]
12 | #define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
| ^
Anna.cpp:70:14: note: 'rpos' was declared here
70 | int lpos,rpos,cur=0,y;
| ^~~~
Anna.cpp:72:9: warning: 'L' may be used uninitialized in this function [-Wmaybe-uninitialized]
72 | if(tmp1[i]+cur>L){
| ^~
Anna.cpp:80:9: warning: 'R' may be used uninitialized in this function [-Wmaybe-uninitialized]
80 | if(tmp1[i]+cur>R){
| ^~
Bruno.cpp: In function 'std::vector<bool> {anonymous}::build(std::vector<int>&)':
Bruno.cpp:25:18: warning: statement has no effect [-Wunused-value]
25 | #define bug(...) 826
| ^~~
Bruno.cpp:41:25: note: in expansion of macro 'bug'
41 | if(stk.empty()) bug(i);
| ^~~
Bruno.cpp: In function 'std::vector<int> {anonymous}::Get(std::vector<int>&, int)':
Bruno.cpp:25:18: warning: statement has no effect [-Wunused-value]
25 | #define bug(...) 826
| ^~~
Bruno.cpp:55:36: note: in expansion of macro 'bug'
55 | if(sz(id)<100) for(auto i: id) bug(i);
| ^~~
Bruno.cpp:55:29: warning: unused variable 'i' [-Wunused-variable]
55 | if(sz(id)<100) for(auto i: id) bug(i);
| ^
Bruno.cpp:25:18: warning: statement has no effect [-Wunused-value]
25 | #define bug(...) 826
| ^~~
Bruno.cpp:57:9: note: in expansion of macro 'bug'
57 | bug(sz(id));
| ^~~
Bruno.cpp:25:18: warning: statement has no effect [-Wunused-value]
25 | #define bug(...) 826
| ^~~
Bruno.cpp:68:13: note: in expansion of macro 'bug'
68 | bug(i);
| ^~~
Bruno.cpp:25:18: warning: statement has no effect [-Wunused-value]
25 | #define bug(...) 826
| ^~~
Bruno.cpp:71:9: note: in expansion of macro 'bug'
71 | bug("B",sz(res));
| ^~~
Bruno.cpp:25:18: warning: statement has no effect [-Wunused-value]
25 | #define bug(...) 826
| ^~~
Bruno.cpp:73:9: note: in expansion of macro 'bug'
73 | bug(val);
| ^~~
Bruno.cpp:25:18: warning: statement has no effect [-Wunused-value]
25 | #define bug(...) 826
| ^~~
Bruno.cpp:75:13: note: in expansion of macro 'bug'
75 | bug(i);
| ^~~
Bruno.cpp:25:18: warning: statement has no effect [-Wunused-value]
25 | #define bug(...) 826
| ^~~
Bruno.cpp:81:9: note: in expansion of macro 'bug'
81 | bug("B",sz(res));
| ^~~
Bruno.cpp: In function 'void InitB(int, std::vector<int>)':
Bruno.cpp:25:18: warning: statement has no effect [-Wunused-value]
25 | #define bug(...) 826
| ^~~
Bruno.cpp:113:5: note: in expansion of macro 'bug'
113 | bug(sz(tree1));
| ^~~
Bruno.cpp: In function 'void ReceiveB(bool)':
Bruno.cpp:25:18: warning: statement has no effect [-Wunused-value]
25 | #define bug(...) 826
| ^~~
Bruno.cpp:141:13: note: in expansion of macro 'bug'
141 | bug(sz(tree2));
| ^~~
Bruno.cpp:157:58: warning: right operand of comma operator has no effect [-Wunused-value]
157 | for(auto i: vec2) minvec.pb(a[i]),bug(i,a[i]);
| ^
Bruno.cpp:25:18: warning: statement has no effect [-Wunused-value]
25 | #define bug(...) 826
| ^~~
Bruno.cpp:159:13: note: in expansion of macro 'bug'
159 | bug(sz(tree2),sz(vec1),sz(vec2));
| ^~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
