제출 #1134517

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1134517		huutuan	Shopping (JOI21_shopping)	C++20	100 / 100	88 ms	12764 KiB

Anna

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

#include <bits/stdc++.h>

using namespace std;

namespace {
   const int SIZE=1954;
   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);
      }
   };
   vector<int> vv;
   int n;
   vector<int> idx;
   CartesianTree tree;
   int L, R, bl, br;
}  // namespace

void InitA(int N, int _L, int _R) {
   n=N; L=_L; R=_R;
   bl=L/SIZE, br=R/SIZE;
   for (int i=0; i<9; ++i) SendA(bl>>i&1);
   for (int i=0; i<9; ++i) SendA(br>>i&1);
   if (bl==br){
      for (int i=0; i<SIZE; ++i) if (bl*SIZE+i<n) idx.push_back(bl*SIZE+i);
   }else{
      for (int i=0; i<SIZE; ++i) if (bl*SIZE+i<n) idx.push_back(bl*SIZE+i);
      int tl=(bl+1)*SIZE, tr=min(n-1, br*SIZE-1);
      idx.push_back(-1);
      for (int i=0; i<SIZE; ++i) if (br*SIZE+i<n) idx.push_back(br*SIZE+i);
   }
}

void ReceiveA(bool x) {
   vv.push_back(x);
   if ((int)vv.size()==(int)idx.size()*2+(bl!=br)*20){
      if (bl!=br){
         int id=0;
         for (int i=0; i<20; ++i) id|=vv[i]<<i;
         vv.erase(vv.begin(), vv.begin()+20);
         auto it=find(idx.begin(), idx.end(), -1);
         if (it!=idx.end()) *it=id;
      }
      tree.build(vv);
   }
}

int Answer() {
   return idx[tree.lca(find(idx.begin(), idx.end(), L)-idx.begin(), find(idx.begin(), idx.end(), R)-idx.begin())];
}

Bruno

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

#include <bits/stdc++.h>

using namespace std;

namespace {
   const int SIZE=1954;
   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);
      }
   };
   vector<int> vv;
   vector<int> a;
   int n;
}  // namespace

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

void ReceiveB(bool y) {
   vv.push_back(y);
   if ((int)vv.size()==18){
      int bl=0, br=0;
      for (int i=0; i<9; ++i) bl|=vv[i]<<i;
      for (int i=0; i<9; ++i) br|=vv[9+i]<<i;
      vector<int> idx;
      if (bl==br){
         for (int i=0; i<SIZE; ++i) if (bl*SIZE+i<n) idx.push_back(bl*SIZE+i);
      }else{
         for (int i=0; i<SIZE; ++i) if (bl*SIZE+i<n) idx.push_back(bl*SIZE+i);
         int tl=(bl+1)*SIZE, tr=min(n-1, br*SIZE-1);
         int id=min_element(a.begin()+tl, a.begin()+tr+1)-a.begin();
         idx.push_back(id);
         for (int i=0; i<SIZE; ++i) if (br*SIZE+i<n) idx.push_back(br*SIZE+i);
         for (int i=0; i<20; ++i) SendB(id>>i&1);
      }
      for (int &i:idx) i=a[i];
      CartesianTree tree;
      tree.build(idx.size(), idx);
      tree.gen_binary();
      for (int i:tree.bin) SendB(i);
   }
}

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