oj.uz

Submission #1074425

# Submission time Handle Problem Language Result Execution time Memory
1074425 2024-08-25T10:28:15 Z TimDee Shopping (JOI21_shopping) C++17
100 / 100
 168 ms 12796 KB 
#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 && rx<=lx+1) 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 (lx==rx) {
    forn(i,min(k,_n-lx*k)) b.pb(lx*k+i);
  } else {
    forn(i,k) b.pb(lx*k+i);
    if (mn!=-1) b.pb(mn);
    forn(i,min(k,_n-rx*k)) b.pb(rx*k+i);
  }
  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) {
    //cout<<x; continue;
    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;
  }
  //cout<<'\n';
  //forn(i,n) cout<<l[i]<<' '<<r[i]<<"  "<<p[i]<<'\n';
  //exit(0);
  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];
    }
  }
}
#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;
    assert(rq < t);

    int mn=-1;
    for(int i=(lq+1)*k; i<rq*k; ++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 (lq!=rq) 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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 664 KB Output is correct
2 Correct 0 ms 664 KB Output is correct
3 Correct 2 ms 664 KB Output is correct
4 Correct 0 ms 916 KB Output is correct
5 Correct 1 ms 664 KB Output is correct
6 Correct 12 ms 920 KB Output is correct
7 Correct 9 ms 664 KB Output is correct
8 Correct 11 ms 756 KB Output is correct
9 Correct 10 ms 664 KB Output is correct
10 Correct 11 ms 924 KB Output is correct
11 Correct 13 ms 920 KB Output is correct
12 Correct 4 ms 664 KB Output is correct
13 Correct 8 ms 756 KB Output is correct
14 Correct 9 ms 756 KB Output is correct
15 Correct 13 ms 756 KB Output is correct
16 Correct 9 ms 772 KB Output is correct
17 Correct 11 ms 664 KB Output is correct
18 Correct 9 ms 664 KB Output is correct
19 Correct 9 ms 664 KB Output is correct
20 Correct 7 ms 664 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 664 KB Output is correct
2 Correct 0 ms 664 KB Output is correct
3 Correct 2 ms 664 KB Output is correct
4 Correct 0 ms 916 KB Output is correct
5 Correct 1 ms 664 KB Output is correct
6 Correct 12 ms 920 KB Output is correct
7 Correct 9 ms 664 KB Output is correct
8 Correct 11 ms 756 KB Output is correct
9 Correct 10 ms 664 KB Output is correct
10 Correct 11 ms 924 KB Output is correct
11 Correct 13 ms 920 KB Output is correct
12 Correct 4 ms 664 KB Output is correct
13 Correct 8 ms 756 KB Output is correct
14 Correct 9 ms 756 KB Output is correct
15 Correct 13 ms 756 KB Output is correct
16 Correct 9 ms 772 KB Output is correct
17 Correct 11 ms 664 KB Output is correct
18 Correct 9 ms 664 KB Output is correct
19 Correct 9 ms 664 KB Output is correct
20 Correct 7 ms 664 KB Output is correct
21 Correct 35 ms 1012 KB Output is correct
22 Correct 28 ms 1036 KB Output is correct
23 Correct 33 ms 920 KB Output is correct
24 Correct 39 ms 1020 KB Output is correct
25 Correct 13 ms 668 KB Output is correct
26 Correct 13 ms 780 KB Output is correct
27 Correct 10 ms 796 KB Output is correct
28 Correct 28 ms 1028 KB Output is correct
29 Correct 29 ms 932 KB Output is correct
30 Correct 20 ms 668 KB Output is correct
31 Correct 20 ms 1032 KB Output is correct
32 Correct 25 ms 916 KB Output is correct
33 Correct 38 ms 920 KB Output is correct
34 Correct 12 ms 664 KB Output is correct
35 Correct 9 ms 1036 KB Output is correct
36 Correct 8 ms 1020 KB Output is correct
37 Correct 13 ms 664 KB Output is correct

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 12380 KB Output is correct
2 Correct 128 ms 12364 KB Output is correct
3 Correct 114 ms 12676 KB Output is correct
4 Correct 104 ms 12688 KB Output is correct
5 Correct 91 ms 12444 KB Output is correct
6 Correct 107 ms 12460 KB Output is correct
7 Correct 98 ms 12604 KB Output is correct
8 Correct 102 ms 12476 KB Output is correct
9 Correct 116 ms 12520 KB Output is correct
10 Correct 95 ms 12600 KB Output is correct
11 Correct 112 ms 12484 KB Output is correct
12 Correct 85 ms 12432 KB Output is correct
13 Correct 83 ms 12524 KB Output is correct
14 Correct 113 ms 12684 KB Output is correct
15 Correct 168 ms 12500 KB Output is correct
16 Correct 89 ms 12328 KB Output is correct
17 Correct 103 ms 12608 KB Output is correct
18 Correct 121 ms 12708 KB Output is correct
19 Correct 96 ms 12588 KB Output is correct
20 Correct 102 ms 12500 KB Output is correct
21 Correct 109 ms 12796 KB Output is correct
22 Correct 92 ms 12592 KB Output is correct
23 Correct 103 ms 12452 KB Output is correct
24 Correct 101 ms 12424 KB Output is correct
25 Correct 97 ms 12452 KB Output is correct
26 Correct 139 ms 12504 KB Output is correct
27 Correct 104 ms 12420 KB Output is correct
28 Correct 103 ms 12340 KB Output is correct
29 Correct 83 ms 12428 KB Output is correct
30 Correct 84 ms 12416 KB Output is correct