Submission #1074380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074380		TimDee	Shopping (JOI21_shopping)	C++17	1 / 100	43 ms	920 KiB

Anna

#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
int lx,rx;
int l,r;
int _n;
void InitA(int n, int l, int r) {
  _n=n;
  int k = 1384;
  lx = l/k;
  rx = r/k;
  ::l=l, ::r=r;
  int ans=0;
  int t = 723;
  for(int i=0; i<lx; ++i) ans+=t-i;
  for(int j=lx; j<rx; ++j) ans++;
  forn(i,18) SendA((ans>>i)&1);
}

int ai=-1;
int num=0;
int mn=-1;
vector<int> s;
void ReceiveA(bool ba) {
  int b = ba;
  if (ai<0 && lx==rx) ai=0;
  if (ai<0) {
    num|=b<<(-ai-1);
    ++ai;
    if (ai==-21) {
      mn = num;
      num = 0;
      ai = 0;
    }
    return;
  }
  s.pb(b);
}

int Answer() {
  int k = 1384;
  vector<int> b; 
  if (mn==-1) {
    forn(i,min(k,_n-lx)) b.pb(lx+i);
  } else {
    forn(i,k) b.pb(lx+1);
    b.pb(mn);
    forn(i,min(k,_n-rx)) b.pb(rx+1);
  }
  b.pb(1e9);
  int n=b.size();
  vector<int> st = {n-1};
  vector<int> l(n,-1), r(n,-1), p(n);
  int nxt=0;
  int last=-1;
  for(auto&x:s) {
    if (x==0) {
      last=st.back();
      st.pop_back();
      continue;
    }
    p[nxt] = st.back();
    r[st.back()] = nxt;
    if (last!=-1) {
      l[nxt] = last;
      p[last] = nxt;
      last = -1;
    }
    st.pb(nxt);
    ++nxt;
  }
  int root = n-1;
  swap(l[root],r[root]);
  while (1) {
    if (::l<=b[root] && b[root]<=::r) return b[root];
    if (b[root] < ::l) {
      root = r[root];
    } else {
      root = l[root];
    }
  }
}

Bruno

#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
const int N=1e6+5;
int a[N];
int n;
void InitB(int n, vector<int> a) {
  forn(i,n) ::a[i]=a[i];
  ::n=n;
}

int rec=0;
int bi=0;
void ReceiveB(bool bx) {
  int x = bx;
  rec+=x<<bi;
  ++bi;
  if (bi==18) {
    int k = 1384;
    int t = 723;

    int lq=0, rq=0;
    for(int i=0; i<t; ++i) {
      if (rec>=t-i) ++lq;
      else break;
      rec-=t-i;
    }
    rq = lq+rec;

    int mn=-1;
    for(int i=(lq+1)*k; i<min(rq*k,n); ++i) {
      if (mn==-1) mn=i;
      if (a[i]<a[mn]) mn=i;
    }
    if (mn!=-1) {
      forn(i,20) SendB((mn>>i)&1);
    }
    vector<int> st={-N};
    for(int i=lq*k; i<min(lq*k+k,n); ++i) {
      while (a[i]<st.back()) {
        SendB(0);
        st.pop_back();
      }
      SendB(1);
      st.pb(a[i]);
    }
    if (mn!=-1) {
      while (a[mn]<st.back()) {
        SendB(0);
        st.pop_back();
      }
      SendB(1);
      st.pb(a[mn]);
    }
    if (rq!=lq) for(int i=rq*k; i<min(rq*k+k,n); ++i) {
      while (a[i]<st.back()) {
        SendB(0);
        st.pop_back();
      }
      SendB(1);
      st.pb(a[i]);
    }
  }
}

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