QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#143108	#3097. Shopping	Mohammed_Atalah	20.755	147ms	14980kb	C++20	4.7kb	2023-08-20 16:45:49	2023-08-20 16:45:50

Judging History

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

[2023-08-20 16:45:50]
评测

测评结果：20.755
用时：147ms
内存：14980kb

查看

[2023-08-20 16:45:49]
提交

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;
  // 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;
}

源文件, 语言: 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)
  {
    // 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();
    }
  }
}

源文件, 语言: C++20

詳細信息

Subtask #1:

score: 1

Accepted

Test #1:

score: 1

Accepted

time: 2ms

memory: 3740kb

input:

output:

-1
0
-1
-1

input:

output:

Accepted: 18 1

result:

ok

Test #2:

score: 1

Accepted

time: 1ms

memory: 3484kb

input:

output:

-1
0
0
-1
-1

input:

output:

Accepted: 18 2

result:

ok

Test #3:

score: 1

Accepted

time: 1ms

memory: 3560kb

input:

output:

input:

output:

Accepted: 18 4

result:

ok

Test #4:

score: 1

Accepted

time: 2ms

memory: 3620kb

input:

output:

input:

output:

Accepted: 18 6

result:

ok

Test #5:

score: 1

Accepted

time: 1ms

memory: 3552kb

input:

output:

input:

output:

Accepted: 18 8

result:

ok

Test #6:

score: 1

Accepted

time: 6ms

memory: 3728kb

input:

output:

input:

output:

Accepted: 18 1945

result:

ok

Test #7:

score: 1

Accepted

time: 2ms

memory: 3660kb

input:

output:

input:

output:

Accepted: 18 1949

result:

ok

Test #8:

score: 1

Accepted

time: 3ms

memory: 3592kb

input:

output:

input:

output:

Accepted: 18 1925

result:

ok

Test #9:

score: 1

Accepted

time: 16ms

memory: 3648kb

input:

output:

input:

output:

Accepted: 18 1988

result:

ok

Test #10:

score: 1

Accepted

time: 3ms

memory: 3508kb

input:

output:

input:

output:

Accepted: 18 1993

result:

ok

Test #11:

score: 1

Accepted

time: 0ms

memory: 3416kb

input:

output:

input:

output:

Accepted: 18 1994

result:

ok

Test #12:

score: 1

Accepted

time: 5ms

memory: 3496kb

input:

output:

input:

output:

Accepted: 18 1000

result:

ok

Test #13:

score: 1

Accepted

time: 0ms

memory: 3408kb

input:

output:

input:

output:

Accepted: 18 1999

result:

ok

Test #14:

score: 1

Accepted

time: 9ms

memory: 3496kb

input:

output:

input:

output:

Accepted: 18 1994

result:

ok

Test #15:

score: 1

Accepted

time: 22ms

memory: 3696kb

input:

output:

input:

output:

Accepted: 18 1997

result:

ok

Test #16:

score: 1

Accepted

time: 0ms

memory: 3764kb

input:

output:

input:

output:

Accepted: 18 1990

result:

ok

Test #17:

score: 1

Accepted

time: 2ms

memory: 3572kb

input:

output:

input:

output:

Accepted: 18 1990

result:

ok

Test #18:

score: 1

Accepted

time: 2ms

memory: 3728kb

input:

output:

input:

output:

Accepted: 18 1991

result:

ok

Test #19:

score: 1

Accepted

time: 2ms

memory: 3744kb

input:

output:

input:

output:

Accepted: 18 1993

result:

ok

Test #20:

score: 1

Accepted

time: 9ms

memory: 3692kb

input:

output:

input:

output:

Accepted: 18 1994

result:

ok

Subtask #2:

score: 9

Accepted

Test #21:

score: 9

Accepted

time: 11ms

memory: 4132kb

input:

output:

input:

output:

Accepted: 18 7849

result:

ok

Test #22:

score: 9

Accepted

time: 13ms

memory: 3960kb

input:

output:

input:

output:

Accepted: 18 3908

result:

ok

Test #23:

score: 9

Accepted

time: 11ms

memory: 4132kb

input:

output:

input:

output:

Accepted: 18 7848

result:

ok

Test #24:

score: 9

Accepted

time: 4ms

memory: 4128kb

input:

output:

input:

output:

Accepted: 18 7846

result:

ok

Test #25:

score: 9

Accepted

time: 9ms

memory: 3740kb

input:

output:

input:

output:

Accepted: 18 3908

result:

ok

Test #26:

score: 9

Accepted

time: 0ms

memory: 4028kb

input:

output:

input:

output:

Accepted: 18 4365

result:

ok

Test #27:

score: 9

Accepted

time: 13ms

memory: 3940kb

input:

output:

input:

output:

Accepted: 18 3935

result:

ok

Test #28:

score: 9

Accepted

time: 12ms

memory: 4108kb

input:

output:

input:

output:

Accepted: 18 7848

result:

ok

Test #29:

score: 9

Accepted

time: 16ms

memory: 3932kb

input:

output:

input:

output:

Accepted: 18 7843

result:

ok

Test #30:

score: 9

Accepted

time: 2ms

memory: 3960kb

input:

output:

input:

output:

Accepted: 18 3904

result:

ok

Test #31:

score: 9

Accepted

time: 6ms

memory: 3844kb

input:

output:

input:

output:

Accepted: 18 7839

result:

ok

Test #32:

score: 9

Accepted

time: 5ms

memory: 3824kb

input:

output:

input:

output:

Accepted: 18 7844

result:

ok

Test #33:

score: 9

Accepted

time: 3ms

memory: 4064kb

input:

output:

input:

output:

Accepted: 18 7841

result:

ok

Test #34:

score: 9

Accepted

time: 0ms

memory: 3876kb

input:

output:

input:

output:

Accepted: 18 3906

result:

ok

Test #35:

score: 9

Accepted

time: 5ms

memory: 4116kb

input:

output:

input:

output:

Accepted: 18 3907

result:

ok

Test #36:

score: 9

Accepted

time: 1ms

memory: 4036kb

input:

output:

input:

output:

Accepted: 18 3906

result:

ok

Test #37:

score: 9

Accepted

time: 13ms

memory: 3748kb

input:

output:

input:

output:

Accepted: 18 3909

result:

ok

Subtask #3:

score: 10.755

Acceptable Answer

Test #38:

score: 10.755

Acceptable Answer

time: 73ms

memory: 14704kb

input:

output:

input:

output:

Accepted: 18 7849

result:

points 0.11950

Test #39:

score: 10.76

Acceptable Answer

time: 147ms

memory: 14952kb

input:

output:

input:

output:

Accepted: 18 7848

result:

points 0.11955555560

Test #40:

score: 35.92

Acceptable Answer

time: 77ms

memory: 14876kb

input:

output:

input:

output:

Accepted: 18 3908

result:

points 0.39911111110

Test #41:

score: 11.025

Acceptable Answer

time: 76ms

memory: 14704kb

input:

output:

input:

output:

Accepted: 18 7795

result:

points 0.12250

Test #42:

score: 20.54

Acceptable Answer

time: 70ms

memory: 14772kb

input:

output:

input:

output:

Accepted: 18 5892

result:

points 0.22822222220

Test #43:

score: 10.76

Acceptable Answer

time: 81ms

memory: 14884kb

input:

output:

input:

output:

Accepted: 18 7848

result:

points 0.11955555560

Test #44:

score: 11.805

Acceptable Answer

time: 75ms

memory: 14804kb

input:

output:

input:

output:

Accepted: 18 7639

result:

points 0.13116666670

Test #45:

score: 10.785

Acceptable Answer

time: 90ms

memory: 14908kb

input:

output:

input:

output:

Accepted: 18 7843

result:

points 0.11983333330

Test #46:

score: 36.17

Acceptable Answer

time: 64ms

memory: 14816kb

input:

output:

input:

output:

Accepted: 18 3883

result:

points 0.40188888890

Test #47:

score: 35.91

Acceptable Answer

time: 77ms

memory: 14876kb

input:

output:

input:

output:

Accepted: 18 3909

result:

points 0.3990

Test #48:

score: 10.755

Acceptable Answer

time: 89ms

memory: 14884kb

input:

output:

input:

output:

Accepted: 18 7849

result:

points 0.11950

Test #49:

score: 36.08

Acceptable Answer

time: 117ms

memory: 14912kb

input:

output:

input:

output:

Accepted: 18 3892

result:

points 0.40088888890

Test #50:

score: 36.11

Acceptable Answer

time: 64ms

memory: 14788kb

input:

output:

input:

output:

Accepted: 18 3889

result:

points 0.40122222220

Test #51:

score: 10.755

Acceptable Answer

time: 52ms

memory: 14980kb

input:

output:

input:

output:

Accepted: 18 7849

result:

points 0.11950

Test #52:

score: 10.755

Acceptable Answer

time: 71ms

memory: 14856kb

input:

output:

input:

output:

Accepted: 18 7849

result:

points 0.11950

Test #53:

score: 20.45

Acceptable Answer

time: 73ms

memory: 14700kb

input:

output:

input:

output:

Accepted: 18 5910

result:

points 0.22722222220

Test #54:

score: 13.875

Acceptable Answer

time: 56ms

memory: 14884kb

input:

output:

input:

output:

Accepted: 18 7225

result:

points 0.15416666670

Test #55:

score: 10.76

Acceptable Answer

time: 64ms

memory: 14720kb

input:

output:

input:

output:

Accepted: 18 7848

result:

points 0.11955555560

Test #56:

score: 10.76

Acceptable Answer

time: 59ms

memory: 14932kb

input:

output:

input:

output:

Accepted: 18 7848

result:

points 0.11955555560

Test #57:

score: 10.76

Acceptable Answer

time: 56ms

memory: 14796kb

input:

output:

input:

output:

Accepted: 18 7848

result:

points 0.11955555560

Test #58:

score: 11.725

Acceptable Answer

time: 82ms

memory: 14708kb

input:

output:

input:

output:

Accepted: 18 7655

result:

points 0.13027777780

Test #59:

score: 17.545

Acceptable Answer

time: 90ms

memory: 14740kb

input:

output:

input:

output:

Accepted: 18 6491

result:

points 0.19494444440

Test #60:

score: 12.795

Acceptable Answer

time: 72ms

memory: 14704kb

input:

output:

input:

output:

Accepted: 18 7441

result:

points 0.14216666670

Test #61:

score: 41.67

Acceptable Answer

time: 81ms

memory: 14772kb

input:

output:

input:

output:

Accepted: 18 3333

result:

points 0.4630

Test #62:

score: 35.95

Acceptable Answer

time: 60ms

memory: 14776kb

input:

output:

input:

output:

Accepted: 18 3905

result:

points 0.39944444440

Test #63:

score: 35.92

Acceptable Answer

time: 65ms

memory: 14788kb

input:

output:

input:

output:

Accepted: 18 3908

result:

points 0.39911111110

Test #64:

score: 35.98

Acceptable Answer

time: 70ms

memory: 14792kb

input:

output:

input:

output:

Accepted: 18 3902

result:

points 0.39977777780

Test #65:

score: 35.9

Acceptable Answer

time: 81ms

memory: 14816kb

input:

output:

input:

output:

Accepted: 18 3910

result:

points 0.39888888890

Test #66:

score: 10.79

Acceptable Answer

time: 74ms

memory: 14948kb

input:

output:

input:

output:

Accepted: 18 7842

result:

points 0.11988888890

Test #67:

score: 35.93

Acceptable Answer

time: 65ms

memory: 14952kb

input:

output:

input:

output:

Accepted: 18 3907

result:

points 0.39922222220