Submission #1135050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135050		huutuan	Shopping (JOI21_shopping)	C++20	100 / 100	176 ms	185064 KiB

Anna

#include "Anna.h"
#include <vector>

#include <bits/stdc++.h>

using namespace std;

namespace Anna{
   const int SIZE=1384, COUNT=723;
   struct SparseTable{
      int n, lg;
      vector<int> a;
      vector<vector<pair<int, int>>> st;
      void build(int _n, const vector<int> &_a){
         n=_n; a=_a;
         lg=0;
         while ((1<<lg)<=n) ++lg;
         st.assign(lg, vector<pair<int, int>>(n, {0, 0}));
         for (int i=0; i<n; ++i) st[0][i]={a[i], i};
         for (int k=1; k<lg; ++k){
            for (int i=0; i+(1<<k)-1<n; ++i){
               st[k][i]=min(st[k-1][i], st[k-1][i+(1<<(k-1))]);
            }
         }
      }
      int get(int l, int r){
         assert(l<=r);
         int k=__lg(r-l+1);
         return min(st[k][l], st[k][r-(1<<k)+1]).second;
      }
   };
   struct CartesianTree{
      int n;
      vector<int> left, right, par, dep;
      vector<int> a;
      SparseTable st;
      vector<int> bin;
      int root;
      void gen_binary(){
         bin.clear();
         auto dfs=[&](auto &&self, int u) -> void {
            if (left[u]!=-1) self(self, left[u]);
            bin.push_back(0);
            if (right[u]!=-1) self(self, right[u]);
            bin.push_back(1);
         };
         dfs(dfs, root);
      }
      void dfs_dep(int u){
         if (left[u]!=-1) dep[left[u]]=dep[u]+1, dfs_dep(left[u]);
         if (right[u]!=-1) dep[right[u]]=dep[u]+1, dfs_dep(right[u]);
      }
      void build(int _n, const vector<int> &_a){
         n=_n, a=_a;
         st.build(n, a);
         left.assign(n, -1);
         right.assign(n, -1);
         par.assign(n, -1);
         dep.assign(n, 0);
         auto dfs=[&](auto &&self, int l, int r) -> int {
            if (l>r) return -1;
            if (l==r) return l;
            int m=st.get(l, r);
            left[m]=self(self, l, m-1);
            right[m]=self(self, m+1, r);
            if (left[m]!=-1) par[left[m]]=m;
            if (right[m]!=-1) par[right[m]]=m;
            return m;
         };
         root=dfs(dfs, 0, n-1);
         gen_binary();
         dfs_dep(root);
      }
      int lca(int u, int v){
         while (dep[u]<dep[v]) v=par[v];
         while (dep[u]>dep[v]) u=par[u];
         while (u!=v) u=par[u], v=par[v];
         return u;
      }
      void build(const vector<int> &_bin){
         bin=_bin;
         n=(int)bin.size()/2;
         vector<int> match(n*2);
         stack<int> st;
         for (int i=0; i<n*2; ++i){
            if (bin[i]==0) st.push(i);
            else match[st.top()]=i, match[i]=st.top(), st.pop();
         }
         left.assign(n, -1);
         right.assign(n, -1);
         par.assign(n, -1);
         dep.assign(n, 0);
         int cnt=0;
         auto dfs=[&](auto &&self, int l, int r) -> int {
            if (l>r) return -1;
            int m=match[r];
            int tl=self(self, l, m-1);
            int u=cnt++;
            int tr=self(self, m+1, r-1);
            left[u]=tl, right[u]=tr;
            if (left[u]!=-1) par[left[u]]=u;
            if (right[u]!=-1) par[right[u]]=u;
            return u;
         };
         root=dfs(dfs, 0, n*2-1);
         dfs_dep(root);
      }
   };
   int encode(pair<int, int> x){
      int ans=0;
      for (int i=0; i<x.first; ++i) ans+=COUNT-i;
      return ans+(x.second-x.first);
   }
   pair<int, int> decode(int x){
      for (int i=0; i<COUNT; ++i){
         if (x<COUNT-i){
            return {i, i+x};
         }
         x-=COUNT-i;
      }
      return {-1, -1};
   }
   vector<int> vv;
   int n;
   vector<int> idx;
   CartesianTree tree;
   int l, r, bl, br;
   int l_bs, r_bs;
   int send_count;
   void fake_SendA(bool y){
      ++send_count;
      SendA(y);
   }
   int tl, tr;
   pair<int, int> pl, pr;
   int get_pos(int x){
      if (pl.first==-1 || x<pl.first-pr.first+1) return pr.first+x;
      return pl.second+(x-(pl.first-pr.first+1));
   }
   int get_len(){
      return pr.second-pr.first+1-max(0, pl.second-pl.first-1);
   }
   int dep, id;
   pair<int, int> find(){
      dep=0, id=1;
      tl=0, tr=n-1;
      while (dep<13 && tl<tr){
         int mid=(tl+tr)>>1;
         if (r<=mid) tr=mid, id<<=1;
         else if (l>=mid+1) tl=mid+1, id<<=1, id|=1;
         else break;
         ++dep;
      }
      l_bs=0, r_bs=tr-tl;
      pl={-1, -1}, pr={tl, tr};
      return {dep, id-(1<<dep)};
   }
   void InitA(int _n, int _l, int _r){
      n=_n, l=_l, r=_r;
      auto t=find();
      if (t.first<=1) fake_SendA(0), fake_SendA(0), fake_SendA(t.first);
      else for (int i=3; i>=0; --i) fake_SendA((t.first+2)>>i&1);
      for (int i=0; i<t.first; ++i) fake_SendA(t.second>>i&1);
   }
   void ReceiveA(bool x){
      vv.push_back(x);
      if (l_bs>=r_bs || send_count==18 || dep==13){
         if (dep==13){
            int array_len=tr-tl+1;
            if ((int)vv.size()==array_len*2){
               tree.build(vv);
               for (int i=tl; i<=tr; ++i) idx.push_back(i);
            }
            return;
         }
         int num=l_bs;
         int lg=__lg(num*2-1);
         int array_len=1+r_bs+1-l_bs;
         if (!l_bs) --array_len;
         int len=array_len*2+(pl.first!=-1)*lg;
         if ((int)vv.size()==len){
            int min_id=-1;
            if (l_bs){
               min_id=0;
               for (int i=0; i<lg; ++i) min_id|=vv[i]<<i;
               min_id+=pl.first;
               vv.erase(vv.begin(), vv.begin()+lg);
            }
            tree.build(vv);
            for (int i=pr.first; i<=pr.second; ++i){
               if (i==min_id) idx.push_back(min_id);
               if (l_bs && pl.first<=i && i<=pl.second) continue;
               idx.push_back(i);
            }
         }
      }else{
         int num=get_len();
         int lg=__lg(num*2-1);
         if ((int)vv.size()==lg){
            int mid=(l_bs+r_bs)>>1;
            int ql=0;
            for (int i=0; i<lg; ++i) ql|=vv[i]<<i;
            ql=get_pos(ql);
            int qr=ql+mid;
            fake_SendA(ql<=l && r<=qr);
            if (ql<=l && r<=qr) r_bs=mid, pr={ql, qr};
            else l_bs=mid+1, pl={ql, qr};
            vv.clear();
         }
      }
   }
   int Answer(){
      return idx[tree.lca(
         lower_bound(idx.begin(), idx.end(), l)-idx.begin(),
         upper_bound(idx.begin(), idx.end(), r)-idx.begin()-1
         )];
   }
}  // namespace

void InitA(int N, int L, int R) {
   Anna::InitA(N, L, R);
}

void ReceiveA(bool x) {
   Anna::ReceiveA(x);
}

int Answer() {
   return Anna::Answer();
}

Bruno

#include "Bruno.h"
#include <vector>

#include <bits/stdc++.h>

using namespace std;


namespace Bruno{
   const int SIZE=1384, COUNT=723;
   struct SparseTable{
      int n, lg;
      vector<int> a;
      vector<vector<pair<int, int>>> st;
      void build(int _n, const vector<int> &_a){
         n=_n; a=_a;
         lg=0;
         while ((1<<lg)<=n) ++lg;
         st.assign(lg, vector<pair<int, int>>(n, {0, 0}));
         for (int i=0; i<n; ++i) st[0][i]={a[i], i};
         for (int k=1; k<lg; ++k){
            for (int i=0; i+(1<<k)-1<n; ++i){
               st[k][i]=min(st[k-1][i], st[k-1][i+(1<<(k-1))]);
            }
         }
      }
      int get(int l, int r){
         assert(l<=r);
         int k=__lg(r-l+1);
         return min(st[k][l], st[k][r-(1<<k)+1]).second;
      }
   };
   struct CartesianTree{
      int n;
      vector<int> left, right, par, dep;
      vector<int> a;
      SparseTable st;
      vector<int> bin;
      int root;
      void gen_binary(){
         bin.clear();
         auto dfs=[&](auto &&self, int u) -> void {
            if (left[u]!=-1) self(self, left[u]);
            bin.push_back(0);
            if (right[u]!=-1) self(self, right[u]);
            bin.push_back(1);
         };
         dfs(dfs, root);
      }
      void dfs_dep(int u){
         if (left[u]!=-1) dep[left[u]]=dep[u]+1, dfs_dep(left[u]);
         if (right[u]!=-1) dep[right[u]]=dep[u]+1, dfs_dep(right[u]);
      }
      void build(int _n, const vector<int> &_a){
         n=_n, a=_a;
         st.build(n, a);
         left.assign(n, -1);
         right.assign(n, -1);
         par.assign(n, -1);
         dep.assign(n, 0);
         auto dfs=[&](auto &&self, int l, int r) -> int {
            if (l>r) return -1;
            if (l==r) return l;
            int m=st.get(l, r);
            left[m]=self(self, l, m-1);
            right[m]=self(self, m+1, r);
            if (left[m]!=-1) par[left[m]]=m;
            if (right[m]!=-1) par[right[m]]=m;
            return m;
         };
         root=dfs(dfs, 0, n-1);
         gen_binary();
         dfs_dep(root);
      }
      int lca(int u, int v){
         while (dep[u]<dep[v]) v=par[v];
         while (dep[u]>dep[v]) u=par[u];
         while (u!=v) u=par[u], v=par[v];
         return u;
      }
      void build(const vector<int> &_bin){
         bin=_bin;
         n=(int)bin.size()/2;
         vector<int> match(n*2);
         stack<int> st;
         for (int i=0; i<n*2; ++i){
            if (bin[i]==0) st.push(i);
            else match[st.top()]=i, match[i]=st.top(), st.pop();
         }
         left.assign(n, -1);
         right.assign(n, -1);
         par.assign(n, -1);
         dep.assign(n, 0);
         int cnt=0;
         auto dfs=[&](auto &&self, int l, int r) -> int {
            if (l>r) return -1;
            int m=match[r];
            int tl=self(self, l, m-1);
            int u=cnt++;
            int tr=self(self, m+1, r-1);
            left[u]=tl, right[u]=tr;
            if (left[u]!=-1) par[left[u]]=u;
            if (right[u]!=-1) par[right[u]]=u;
            return u;
         };
         root=dfs(dfs, 0, n*2-1);
         dfs_dep(root);
      }
   };
   int encode(pair<int, int> x){
      int ans=0;
      for (int i=0; i<x.first; ++i) ans+=COUNT-i;
      return ans+(x.second-x.first);
   }
   pair<int, int> decode(int x){
      for (int i=0; i<COUNT; ++i){
         if (x<COUNT-i){
            return {i, i+x};
         }
         x-=COUNT-i;
      }
      return {-1, -1};
   }
   int n;
   vector<int> a;
   vector<int> vv;
   int cnt;
   int bl, br;
   int dep, id;
   int sz_dep;
   vector<pair<int, int>> v;
   CartesianTree tree;
   void InitB(int _n, vector<int> _a){
      n=_n; a=_a;
   }
   int tl, tr;
   void find(){
      int cdep=0, cid=1;
      tl=0, tr=n-1;
      while (cdep<dep){
         int mid=(tl+tr)>>1;
         if (!(id>>(dep-cdep-1)&1)) tr=mid, cid<<=1;
         else tl=mid+1, cid<<=1, cid|=1;
         ++cdep;
      }
   }
   int l_bs, r_bs;
   void send(int x, int num){
      int lg=__lg(num*2-1);
      for (int i=0; i<lg; ++i) SendB(x>>i&1);
   }
   pair<int, int> pl, pr;
   int get_pos(int x){
      if (pl.first==-1 || x<=pl.first) return x-pr.first;
      return pl.first-pr.first+1+x-pl.second;
   }
   int get_len(){
      return pr.second-pr.first+1-max(0, pl.second-pl.first-1);
   }
   bool check=0;
   void ReceiveB(bool y){
      vv.push_back(y);
      ++cnt;
      if ((int)vv.size()==2){
         if (vv[0]==0 && vv[1]==0) sz_dep=3;
         else sz_dep=4;
      }
      if ((int)vv.size()==sz_dep){
         if (sz_dep==3) dep=vv[2];
         else{
            for (int i=0; i<4; ++i) dep|=vv[3-i]<<i;
            dep-=2;
         }
      }
      if ((int)vv.size()==sz_dep+dep){
         for (int i=0; i<dep; ++i) id|=vv[sz_dep+i]<<i;
         id+=1<<dep;
         find();
         if (dep==13){
            vector<int> val;
            for (int i=tl; i<=tr; ++i){
               val.push_back(a[i]);
            }
            tree.build(val.size(), val);
            tree.gen_binary();
            for (int i:tree.bin) SendB(i);
            return;
         }
         int pos=(tl+tr)>>1;
         int l=pos, r=pos;
         while (1){
            v.emplace_back(l, r);
            if (l==tl && r==tr) break;
            if (l==tl || (r<tr && a[r+1]>a[l-1])) ++r;
            else --l;
         }
         l_bs=0, r_bs=(int)v.size()-1;
         pl={-1, -1}, pr={tl, tr};
         if (l_bs<r_bs){
            int mid=(l_bs+r_bs)>>1;
            send(get_pos(v[mid].first), get_len());
         }
         if (l_bs>=r_bs || cnt==18){
            SparseTable st; st.build(n, a);
            int min_id=-1;
            if (l_bs){
               min_id=st.get(pl.first, pl.second);
               send(min_id-pl.first, l_bs);
            }
            vector<int> val;
            for (int i=v[r_bs].first; i<=v[r_bs].second; ++i){
               if (i==min_id) val.push_back(a[i]);
               if (l_bs && pl.first<=i && i<=pl.second) continue;
               val.push_back(a[i]);
            }
            tree.build(val.size(), val);
            tree.gen_binary();
            for (int i:tree.bin) SendB(i);
         }
         check=1;
      }
      if (check && (int)vv.size()>sz_dep+dep){
         int mid=(l_bs+r_bs)>>1;
         if (y) r_bs=mid, pr=v[mid];
         else l_bs=mid+1, pl=v[mid];
         if (l_bs>=r_bs || cnt==18){
            SparseTable st; st.build(n, a);
            int min_id=-1;
            if (l_bs){
               min_id=st.get(pl.first, pl.second);
               send(min_id-pl.first, l_bs);
            }
            vector<int> val;
            for (int i=v[r_bs].first; i<=v[r_bs].second; ++i){
               if (i==min_id) val.push_back(a[i]);
               if (l_bs && pl.first<=i && i<=pl.second) continue;
               val.push_back(a[i]);
            }
            tree.build(val.size(), val);
            tree.gen_binary();
            for (int i:tree.bin) SendB(i);
         }else{
            int mid=(l_bs+r_bs)>>1;
            send(get_pos(v[mid].first), get_len());
         }
      }
   }
}  // namespace

void InitB(int N, std::vector<int> P) {
   Bruno::InitB(N, P);
}

void ReceiveB(bool y) {
   Bruno::ReceiveB(y);
}

• Subtask 1: 1 / 1
• Subtask 2: 9 / 9
• Subtask 3: 90 / 90