oj.uz

Submission #974163

# Submission time Handle Problem Language Result Execution time Memory
974163 2024-05-03T02:34:59 Z nguyentunglam Shopping (JOI21_shopping) C++17
100 / 100
 131 ms 60080 KB 
#include "Anna.h"
#include <vector>
#include<bits/stdc++.h>
//#define cout cerr
using namespace std;

namespace anna{

const int M = 18;
int cnt, n, l, r;

int _from, _to, cnt_bit;

int from, to, ed, ans;

stack<int> st;

vector<int> lst, bit;

int x = -1, y = -1;

int p = 0, mn = 0;

vector<pair<int, int> > arr[30];

int phase = 0;

void build(int d, int l, int r) {
  arr[d].emplace_back(l, r);
  if (l != r) {
    int mid = l + r >> 1;
    build(d + 1, l, mid);
    build(d + 1, mid + 1, r);
  }
}
}  // namespace
using namespace anna;

void InitA(int N, int ll, int rr) {
  n = N;
  l = ll;
  r = rr;
  build(0, 0, n - 1);
  for(int depth = 14; depth >= 0; depth--) {
    int cover = -1;
    for(int i = 0; i < arr[depth].size(); i++) {
      int L, R; tie(L, R) = arr[depth][i];
      if (L <= l && r <= R) {
        cover = i;
        x = L;
        y = R;
      }
    }
    if (cover == -1) continue;
    for(int i = 0; i < 4; i++) SendA(depth >> i & 1), cnt++;
    for(int i = 0; i < depth; i++) SendA(cover >> i & 1), cnt++;
//    cout << cover << endl;
    assert((1 << depth) > cover);
//    cout << cnt << endl;
//    cout << depth << endl;
////    cout << from << " " << to << endl;
//    cout << x << " " << y << endl;
    break;
  }

//  assert(x >= 0);
  from = to = x + y >> 1;
//  assert(from >= l && to <= r);
  cnt_bit = log2(1LL * (from - x + 1) * (y - to + 1));
//  cout << cnt_bit << endl;
//  cout << cnt << " " << from - x + 1 << " " << (to - endl;
//  cout << depth << endl;
//  cout << from << " " << to << endl;
//  cout << x << " " << y << endl;
//  exit(0);
}

void ReceiveA(bool X) {
//  cerr << X << endl;
  bit.push_back(X);
  if (cnt < M && bit.size() == cnt_bit + 1) {
    long long code = 0;
    for(int i = 0; i <= cnt_bit; i++) if (bit[i]) code |= (1LL << i);
//    for(int i = 0; i <= cnt_bit; i++) cout << bit[i]; cout << endl;
    bit.clear();
    int _from = x + code / (y - to + 1);
    int _to = to + code % (y - to + 1);
//    cout << "A " << _from << " " << _to << " " << from << " " << to << " " << x << " " << y << " " << code << endl;
    if (_from <= l && r <= _to) {
      x = _from;
      y = _to;
//      cout << cnt_bit << endl;
      SendA(1);
    }
    else {
      SendA(0);
      from = _from;
      to = _to;
    }
    cnt++;
    cnt_bit = log2(1LL * (from - x + 1) * (y - to + 1));
  }
//  cout << cnt << endl;
//  cout << 1 << endl;
  else if (phase == 0 && cnt == M && bit.size() == 20) {
//    exit(0);
    for(int i = 0; i < 20; i++) if (bit[i]) mn |= (1 << i);
    for(int i = x; i < from; i++) lst.push_back(i);
    lst.push_back(mn);
    for(int i = to + 1; i <= y; i++) lst.push_back(i);
//    cout << mn << endl;
//    cout << lst.size() << endl;
//    cout << mn << endl;
//    exit(0);
    phase = 1;
  }
  else if (phase == 1) {
//    cout << ed << endl;
//    cout << X << endl;
//    exit(0);
    if (X == 0) st.pop();
    else {
      st.push(lst[p]);
//      cout << lst[p] << " " << ed << endl;
//      exit(0);
      if (p == lst.size() - 1 || lst[p + 1] > r) {
        ans = -1;
        while (!st.empty() && st.top() >= l) {
          ans = st.top();
          st.pop();
        }
//        assert(ans >= l && ans <= r);
//        assert(ans >= 0);
//        cout << ans << endl;
//        exit(0);
        phase = 2;
      }
      p++;
    }
  }
}

int Answer() {
  return ans;
}

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

namespace bruno {

const int N = 1e6 + 10, M = 18;
int n, cnt_anna;

int a[N];

int L, R, _from, _to;

int x, y, from, to;

int phase, depth;

vector<bool> bit;

vector<pair<int, int> > seg;

vector<pair<int, int> > arr[30];

void build(int d, int l, int r) {
  arr[d].emplace_back(l, r);
  if (l != r) {
    int mid = l + r >> 1;
    build(d + 1, l, mid);
    build(d + 1, mid + 1, r);
  }
}

void InitB(int N, std::vector<int> P) {
  n = N;
  for(int i = 0; i < n; i++) a[i] = P[i];
}

void handle () {
  int mid = L + R >> 1;
  tie(_from, _to) = seg[mid];
  long long code = 1LL * (_from - x) * (y - to + 1) + _to - to;
//  cout << "B " << _from << " " << _to << " " << from << " " << to << " " << x << " " << y << " " << code << endl;
  int last = 0;
  for(int i = 0; (1LL << i) <= 1LL * (from - x + 1) * (y - to + 1); i++) SendB(code >> i & 1), last = i;
//  cout << last << endl;
}

void ReceiveB(bool Y) {
  cnt_anna++;
  bit.push_back(Y);
  if (phase == 0 && bit.size() == 4) {
    depth = 0;
    for(int i = 0; i < 4; i++) if (bit[i]) depth |= (1 << i);
    bit.clear();
    phase = 1;
//    cout << depth << endl;
//    exit(0);
  }
  if (phase == 1 && bit.size() == depth) {
//    cout << 1 << endl;
    build(0, 0, n - 1);
    int idx = 0;
    for(int i = 0; i < depth; i++) if (bit[i]) idx |= (1 << i);
    bit.clear();
    tie(x, y) = arr[depth][idx];
    from = to = x + y >> 1;
//    cout << from << " " << to << " " << x << " " << y << endl;
//    exit(0);
    pair<int, int> old = make_pair(from, to);
    while (from >= x && to <= y) {
      seg.emplace_back(from, to);
      if (from > x && (to == y || a[from - 1] > a[to + 1])) from--;
      else to++;
    }
    tie(from, to) = old;
    L = 0, R = seg.size() - 1;
//    cout << cnt_anna << endl;
    if (cnt_anna < M) handle();
    phase = 2;
  }
  else if (phase == 2) {
    int mid = L + R >> 1;
    if (Y) {
      x = _from;
      y = _to;
      R = mid;
    }
    else {
      from = _from;
      to = _to;
      L = mid;
    }
    if (cnt_anna < M) handle();
  }
  if (cnt_anna >= M) {
//    cout << from << " " << to << " " << x << " " << y << endl;
//    exit(0);
    vector<int> lst;
    for(int i = x; i < from; i++) lst.push_back(a[i]);
    int mn = from;
    for(int i = from; i <= to; i++) if (a[i] < a[mn]) mn = i;
    for(int i = 0; i < 20; i++) SendB(mn >> i & 1);
    lst.push_back(a[mn]);
    for(int i = to + 1; i <= y; i++) lst.push_back(a[i]);
//    cout << lst.size() << endl;
//    exit(0);
    stack<int> st;
    for(int i = 0; i < lst.size(); i++) {
      while (!st.empty() && lst[st.top()] >= lst[i]) st.pop(), SendB(0);
      SendB(1);
      st.push(i);
    }
//    exit(0);
  }
}

}  // namespace

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

void ReceiveB(bool Y) {
  bruno::ReceiveB(Y);
}

Compilation message

Anna.cpp: In function 'void anna::build(int, int, int)':
Anna.cpp:31:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |     int mid = l + r >> 1;
      |               ~~^~~
Anna.cpp: In function 'void InitA(int, int, int)':
Anna.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i = 0; i < arr[depth].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~~~~
Anna.cpp:67:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |   from = to = x + y >> 1;
      |               ~~^~~
Anna.cpp: In function 'void ReceiveA(bool)':
Anna.cpp:81:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |   if (cnt < M && bit.size() == cnt_bit + 1) {
      |                  ~~~~~~~~~~~^~~~~~~~~~~~~~
Anna.cpp:126:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |       if (p == lst.size() - 1 || lst[p + 1] > r) {
      |           ~~^~~~~~~~~~~~~~~~~

Bruno.cpp: In function 'void bruno::build(int, int, int)':
Bruno.cpp:29:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     int mid = l + r >> 1;
      |               ~~^~~
Bruno.cpp: In function 'void bruno::handle()':
Bruno.cpp:41:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |   int mid = L + R >> 1;
      |             ~~^~~
Bruno.cpp:45:7: warning: variable 'last' set but not used [-Wunused-but-set-variable]
   45 |   int last = 0;
      |       ^~~~
Bruno.cpp: In function 'void bruno::ReceiveB(bool)':
Bruno.cpp:61:32: warning: comparison of integer expressions of different signedness: 'std::vector<bool>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |   if (phase == 1 && bit.size() == depth) {
      |                     ~~~~~~~~~~~^~~~~~~~
Bruno.cpp:68:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |     from = to = x + y >> 1;
      |                 ~~^~~
Bruno.cpp:84:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |     int mid = L + R >> 1;
      |               ~~^~~
Bruno.cpp:110:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for(int i = 0; i < lst.size(); i++) {
      |                    ~~^~~~~~~~~~~~

Subtask #1
1.0 / 1.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 664 KB Output is correct
2 Correct 1 ms 916 KB Output is correct
3 Correct 1 ms 916 KB Output is correct
4 Correct 2 ms 664 KB Output is correct
5 Correct 1 ms 664 KB Output is correct
6 Correct 1 ms 664 KB Output is correct
7 Correct 1 ms 664 KB Output is correct
8 Correct 2 ms 920 KB Output is correct
9 Correct 2 ms 664 KB Output is correct
10 Correct 2 ms 664 KB Output is correct
11 Correct 1 ms 664 KB Output is correct
12 Correct 1 ms 664 KB Output is correct
13 Correct 1 ms 664 KB Output is correct
14 Correct 2 ms 664 KB Output is correct
15 Correct 2 ms 664 KB Output is correct
16 Correct 1 ms 920 KB Output is correct
17 Correct 2 ms 664 KB Output is correct
18 Correct 2 ms 920 KB Output is correct
19 Correct 1 ms 664 KB Output is correct
20 Correct 2 ms 920 KB Output is correct
21 Correct 3 ms 1748 KB Output is correct
22 Correct 3 ms 1464 KB Output is correct
23 Correct 3 ms 1560 KB Output is correct
24 Correct 3 ms 1492 KB Output is correct
25 Correct 3 ms 1392 KB Output is correct
26 Correct 2 ms 1748 KB Output is correct
27 Correct 3 ms 1492 KB Output is correct
28 Correct 2 ms 1560 KB Output is correct
29 Correct 3 ms 1752 KB Output is correct
30 Correct 2 ms 1376 KB Output is correct
31 Correct 2 ms 1468 KB Output is correct
32 Correct 2 ms 1456 KB Output is correct
33 Correct 2 ms 1416 KB Output is correct
34 Correct 3 ms 1380 KB Output is correct
35 Correct 3 ms 1396 KB Output is correct
36 Correct 2 ms 1388 KB Output is correct
37 Correct 2 ms 1552 KB Output is correct

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 57628 KB Output is correct
2 Correct 121 ms 48600 KB Output is correct
3 Correct 119 ms 46848 KB Output is correct
4 Correct 127 ms 57912 KB Output is correct
5 Correct 127 ms 58688 KB Output is correct
6 Correct 129 ms 58056 KB Output is correct
7 Correct 123 ms 46156 KB Output is correct
8 Correct 115 ms 48192 KB Output is correct
9 Correct 120 ms 47388 KB Output is correct
10 Correct 114 ms 49040 KB Output is correct
11 Correct 129 ms 60080 KB Output is correct
12 Correct 112 ms 48524 KB Output is correct
13 Correct 115 ms 50700 KB Output is correct
14 Correct 115 ms 47680 KB Output is correct
15 Correct 126 ms 47680 KB Output is correct
16 Correct 121 ms 51336 KB Output is correct
17 Correct 129 ms 49096 KB Output is correct
18 Correct 117 ms 46904 KB Output is correct
19 Correct 126 ms 47208 KB Output is correct
20 Correct 118 ms 47508 KB Output is correct
21 Correct 126 ms 49476 KB Output is correct
22 Correct 121 ms 46592 KB Output is correct
23 Correct 120 ms 47584 KB Output is correct
24 Correct 117 ms 46020 KB Output is correct
25 Correct 122 ms 46140 KB Output is correct
26 Correct 118 ms 46148 KB Output is correct
27 Correct 115 ms 47564 KB Output is correct
28 Correct 115 ms 46312 KB Output is correct
29 Correct 127 ms 46780 KB Output is correct
30 Correct 118 ms 46672 KB Output is correct