oj.uz

Submission #831422

# Submission time Handle Problem Language Result Execution time Memory
831422 2023-08-20T08:47:29 Z Mohammed_Atalah Shopping (JOI21_shopping) C++17
100 / 100
 177 ms 12372 KB 
#include "Anna.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
namespace
{

  int N, L, R;
  int cnt;
  vector<int> status;
  int res;
  stack<int> s;
  vector<int> Left;
  vector<int> Right;
  int last = -1;
  int root = 0;
  int sz = 0;
  int idxmid = 0;
} // namespace

void InitA(int N, int L, int R)
{
  ::N = N;
  ::L = L;
  ::R = R;
  res = L;
  // cout << 5 / 3 << endl;
  Left.resize((1957 * 2) + 1, -1);
  Right.resize((1957 * 2) + 1, -1);
  cnt = 0;
  int l = L / 1957;
  int r = R / 1957;

  for (int i = 0; i <= 8; i++)
  {
    if ((l >> i) & 1)
    {
      SendA(1);
    }
    else
    {
      SendA(0);
    }
  }
  for (int i = 0; i <= 8; i++)
  {
    if ((r >> i) & 1)
    {
      SendA(1);
    }
    else
    {
      SendA(0);
    }
  }
  if (r == l)
  {
    sz = min(1957, N);
  }
  else
  {
    sz = 1957 + min(1957, N - (r * 1957)) + 1;
  }

  // cout << L << ' ' << R << endl;
}

int get_idx(int idx)
{
  if (L / 1957 == R / 1957)
  {
    return ((L / 1957) * 1957) + idx;
  }

  if (idx < 1957)
  {
    return ((L / 1957) * 1957) + idx;
  }
  else if (idx == sz - 1)
  {
    return idxmid;
  }
  else
  {
    return ((R / 1957) * 1957) + idx - 1957;
  }
}

void solve()
{

  // for (int i = 0; i < sz; i++)
  // {
  //   cout << i << " " << Left[i] << " " << Right[i] << endl;
  // }
  int e = get_idx(root);
  // cout << root << endl;
  while (e > R || e < L)
  {
    if (e > R)
    {
      root = Left[root];
    }
    else
    {
      root = Right[root];
    }
    e = get_idx(root);
  }
  res = e;
}
void ReceiveA(bool x)
{
  // cout << "Hello" << endl;
  if (cnt < sz)
  {
    if (x)
    {
      last = s.top();
      s.pop();
    }
    else
    {
      if (s.empty())
      {
        if (cnt)
        {
          Left[cnt] = last;
        }
        root = cnt;
        s.push(cnt);
      }
      else if (last == -1)
      {
        Right[s.top()] = cnt;
        s.push(cnt);
      }
      else
      {
        Left[cnt] = last;
        Right[s.top()] = cnt;
        s.push(cnt);
      }

      last = -1;
      cnt++;
    }
  }
  else
  {
    if (x)
      idxmid += pow(2, cnt - sz);

    cnt++;
  }

  // cout << cnt << endl;
  if ((cnt == sz + 20 && L / 1957 != R / 1957) || (cnt == sz && L / 1957 == R / 1957))
  {
    solve();
  }
}

int Answer()
{
  return res;
}

#include "Bruno.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;

namespace
{
  int N;
  vector<int> nums;
  int cnt = 0;
  int L = 0;
  int R = 0;
}

void minel()
{
  vector<int> v;
  int idxmid = -1;
  if (L == R)
  {
    for (int i = L * 1957; i <= min((L * 1957) + 1956, N - 1); i++)
    {
      // cout << i << endl;
      v.push_back(nums[i]);
    }
  }
  else
  {
    for (int i = L * 1957; i <= (L * 1957) + 1956; i++)
    {
      v.push_back(nums[i]);
    }
    for (int i = R * 1957; i <= min((R * 1957) + 1956, N - 1); i++)
    {
      v.push_back(nums[i]);
    }
    int mn = 1e7;
    for (int i = (L * 1957) + 1957; i < R * 1957; i++)
    {
      if (nums[i] < mn)
      {
        mn = nums[i];
        idxmid = i;
      }
    }
    v.push_back(mn);
  }

  /////////

  int n = v.size();
  int root = -1;
  stack<int> s;
  vector<int> left(n, -1);
  vector<int> right(n, -1);
  // cout << n << endl;
  for (int i = 0; i < n; i++)
  {

    if (s.empty())
    {
      root = i;
      s.push(i);
      SendB(0);
      continue;
    }
    int last = -1;
    while (!s.empty() && v[s.top()] > v[i])
    {
      last = s.top();
      s.pop();
      SendB(1);
    }

    if (last == -1)
    {
      right[s.top()] = i;
      s.push(i);
      SendB(0);
    }
    else if (s.empty())
    {
      left[i] = last;
      root = i;
      s.push(i);
      SendB(0);
    }
    else
    {
      left[i] = last;
      right[s.top()] = i;
      s.push(i);
      SendB(0);
    }
  }
  // for (int i = 0; i < n; i++)
  // {
  //   cout << i << " " << left[i] << " " << right[i] << endl;
  // }
  if (L != R)
  {
    for (int i = 0; i < 20; i++)
    {
      if ((idxmid >> i) & 1)
      {
        SendB(1);
      }
      else
      {
        SendB(0);
      }
    }
  }
}

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

void ReceiveB(bool y)
{

  if (cnt <= 8)
  {
    // cout << 1 << endl;
    if (y)
      L += pow(2, cnt);
    cnt++;
  }
  else if (cnt <= 17)
  {
    // cout << 2 << endl;
    if (y)
      R += pow(2, cnt - 9);
    cnt++;
    if (cnt == 18)
    {
      // cout << L << " " << R << endl;
      minel();
    }
  }
}

Compilation message

Bruno.cpp: In function 'void minel()':
Bruno.cpp:52:7: warning: variable 'root' set but not used [-Wunused-but-set-variable]
   52 |   int root = -1;
      |       ^~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 400 KB Output is correct
2 Correct 1 ms 400 KB Output is correct
3 Correct 0 ms 400 KB Output is correct
4 Correct 0 ms 400 KB Output is correct
5 Correct 0 ms 400 KB Output is correct
6 Correct 9 ms 400 KB Output is correct
7 Correct 15 ms 400 KB Output is correct
8 Correct 12 ms 500 KB Output is correct
9 Correct 11 ms 400 KB Output is correct
10 Correct 11 ms 400 KB Output is correct
11 Correct 17 ms 400 KB Output is correct
12 Correct 9 ms 508 KB Output is correct
13 Correct 9 ms 400 KB Output is correct
14 Correct 12 ms 496 KB Output is correct
15 Correct 11 ms 400 KB Output is correct
16 Correct 9 ms 400 KB Output is correct
17 Correct 9 ms 400 KB Output is correct
18 Correct 12 ms 400 KB Output is correct
19 Correct 18 ms 484 KB Output is correct
20 Correct 19 ms 400 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 400 KB Output is correct
2 Correct 1 ms 400 KB Output is correct
3 Correct 0 ms 400 KB Output is correct
4 Correct 0 ms 400 KB Output is correct
5 Correct 0 ms 400 KB Output is correct
6 Correct 9 ms 400 KB Output is correct
7 Correct 15 ms 400 KB Output is correct
8 Correct 12 ms 500 KB Output is correct
9 Correct 11 ms 400 KB Output is correct
10 Correct 11 ms 400 KB Output is correct
11 Correct 17 ms 400 KB Output is correct
12 Correct 9 ms 508 KB Output is correct
13 Correct 9 ms 400 KB Output is correct
14 Correct 12 ms 496 KB Output is correct
15 Correct 11 ms 400 KB Output is correct
16 Correct 9 ms 400 KB Output is correct
17 Correct 9 ms 400 KB Output is correct
18 Correct 12 ms 400 KB Output is correct
19 Correct 18 ms 484 KB Output is correct
20 Correct 19 ms 400 KB Output is correct
21 Correct 57 ms 528 KB Output is correct
22 Correct 25 ms 608 KB Output is correct
23 Correct 60 ms 620 KB Output is correct
24 Correct 33 ms 620 KB Output is correct
25 Correct 41 ms 592 KB Output is correct
26 Correct 39 ms 604 KB Output is correct
27 Correct 25 ms 704 KB Output is correct
28 Correct 40 ms 628 KB Output is correct
29 Correct 72 ms 736 KB Output is correct
30 Correct 23 ms 588 KB Output is correct
31 Correct 40 ms 616 KB Output is correct
32 Correct 46 ms 616 KB Output is correct
33 Correct 36 ms 528 KB Output is correct
34 Correct 26 ms 592 KB Output is correct
35 Correct 33 ms 592 KB Output is correct
36 Correct 22 ms 588 KB Output is correct
37 Correct 32 ms 528 KB Output is correct

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 12084 KB Output is correct
2 Correct 177 ms 12280 KB Output is correct
3 Correct 100 ms 12184 KB Output is correct
4 Correct 97 ms 12264 KB Output is correct
5 Correct 146 ms 12372 KB Output is correct
6 Correct 135 ms 12264 KB Output is correct
7 Correct 135 ms 12216 KB Output is correct
8 Correct 158 ms 12272 KB Output is correct
9 Correct 95 ms 12276 KB Output is correct
10 Correct 97 ms 12204 KB Output is correct
11 Correct 138 ms 12232 KB Output is correct
12 Correct 113 ms 12272 KB Output is correct
13 Correct 106 ms 12268 KB Output is correct
14 Correct 125 ms 12172 KB Output is correct
15 Correct 133 ms 12192 KB Output is correct
16 Correct 105 ms 12224 KB Output is correct
17 Correct 148 ms 12312 KB Output is correct
18 Correct 123 ms 12228 KB Output is correct
19 Correct 115 ms 12312 KB Output is correct
20 Correct 131 ms 12308 KB Output is correct
21 Correct 96 ms 12228 KB Output is correct
22 Correct 99 ms 12216 KB Output is correct
23 Correct 149 ms 12308 KB Output is correct
24 Correct 100 ms 12312 KB Output is correct
25 Correct 104 ms 12272 KB Output is correct
26 Correct 90 ms 12192 KB Output is correct
27 Correct 106 ms 12272 KB Output is correct
28 Correct 123 ms 12276 KB Output is correct
29 Correct 137 ms 12264 KB Output is correct
30 Correct 104 ms 12264 KB Output is correct