QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#142846	#3097. Shopping	Mohammed_Atalah	1	71ms	14880kb	C++20	4.5kb	2023-08-20 00:27:19	2023-08-20 00:27:22

Judging History

你现在查看的是最新测评结果

[2023-08-20 00:27:22]
评测

测评结果：1
用时：71ms
内存：14880kb

查看

[2023-08-20 00:27:19]
提交

Anna

#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;
  Left.resize(N, -1);
  Right.resize(N, -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);

    cnt++;
  }

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

int Answer()
{
  return res;
}

源文件, 语言: C++20

Bruno

#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)
  {
    if (y)
      L += pow(2, cnt);
    cnt++;
  }
  else if (cnt <= 16)
  {
    if (y)
      R += pow(2, cnt - 9);
    cnt++;
  }
  else
  {
    // cout << L << " " << R << endl;
    minel();
  }
}

源文件, 语言: C++20

詳細信息

Subtask #1:

score: 1

Accepted

Test #1:

score: 1

Accepted

time: 1ms

memory: 3556kb

input:

output:

-1
0
-1
-1

input:

output:

Accepted: 18 1

result:

ok

Test #2:

score: 1

Accepted

time: 1ms

memory: 3632kb

input:

output:

-1
0
0
-1
-1

input:

output:

Accepted: 18 2

result:

ok

Test #3:

score: 1

Accepted

time: 0ms

memory: 3752kb

input:

output:

input:

output:

Accepted: 18 4

result:

ok

Test #4:

score: 1

Accepted

time: 1ms

memory: 3740kb

input:

output:

input:

output:

Accepted: 18 6

result:

ok

Test #5:

score: 1

Accepted

time: 2ms

memory: 3704kb

input:

output:

input:

output:

Accepted: 18 8

result:

ok

Test #6:

score: 1

Accepted

time: 20ms

memory: 3648kb

input:

output:

input:

output:

Accepted: 18 1945

result:

ok

Test #7:

score: 1

Accepted

time: 0ms

memory: 3512kb

input:

output:

input:

output:

Accepted: 18 1949

result:

ok

Test #8:

score: 1

Accepted

time: 8ms

memory: 3580kb

input:

output:

input:

output:

Accepted: 18 1925

result:

ok

Test #9:

score: 1

Accepted

time: 10ms

memory: 3768kb

input:

output:

input:

output:

Accepted: 18 1988

result:

ok

Test #10:

score: 1

Accepted

time: 11ms

memory: 3744kb

input:

output:

input:

output:

Accepted: 18 1993

result:

ok

Test #11:

score: 1

Accepted

time: 1ms

memory: 3408kb

input:

output:

input:

output:

Accepted: 18 1994

result:

ok

Test #12:

score: 1

Accepted

time: 5ms

memory: 3776kb

input:

output:

input:

output:

Accepted: 18 1000

result:

ok

Test #13:

score: 1

Accepted

time: 0ms

memory: 3488kb

input:

output:

input:

output:

Accepted: 18 1999

result:

ok

Test #14:

score: 1

Accepted

time: 4ms

memory: 3656kb

input:

output:

input:

output:

Accepted: 18 1994

result:

ok

Test #15:

score: 1

Accepted

time: 7ms

memory: 3572kb

input:

output:

input:

output:

Accepted: 18 1997

result:

ok

Test #16:

score: 1

Accepted

time: 2ms

memory: 3744kb

input:

output:

input:

output:

Accepted: 18 1990

result:

ok

Test #17:

score: 1

Accepted

time: 9ms

memory: 3496kb

input:

output:

input:

output:

Accepted: 18 1990

result:

ok

Test #18:

score: 1

Accepted

time: 0ms

memory: 3588kb

input:

output:

input:

output:

Accepted: 18 1991

result:

ok

Test #19:

score: 1

Accepted

time: 4ms

memory: 3408kb

input:

output:

input:

output:

Accepted: 18 1993

result:

ok

Test #20:

score: 1

Accepted

time: 8ms

memory: 3764kb

input:

output:

input:

output:

Accepted: 18 1994

result:

ok

Subtask #2:

score: 0

Interactor Runtime Error

Test #21:

score: 0

Interactor Runtime Error

input:

output:

input:

output:

result:

Subtask #3:

score: 0

Wrong Answer

Test #38:

score: 0

Wrong Answer

time: 71ms

memory: 14880kb

input:

output:

input:

output:

Wrong Answer [2]

result:

wrong answer