Submission #947512

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
947512	2024-03-16T10:23:31 Z	marvinthang	Shopping (JOI21_shopping)	C++17	100 / 100	106 ms	16616 KB

Anna
Bruno

/*************************************
*    author: marvinthang             *
*    created: 16.03.2024 15:47:41    *
*************************************/

#include "Anna.h"
#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i-- > 0; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

// end of template

namespace {
	int N, L, R, cnt_r, cnt_s;
	int l, r, pl, pr, px, py, pm, p;
	bool phase;
	vector <int> num_pop;
}

void InitA(int n, int _l, int _r) {
	N = n; L = _l; R = _r + 1;
	cnt_r = 0;
	if (R - L > 1) {
		l = 0;
		r = N;
		int i = 1, d = 0;
		while (d < 14) {
			int m = l + r >> 1;
			if (R <= m) r = m, i <<= 1;
			else if (L >= m) l = m, i = i << 1 | 1;
			else break;
			++d;
		}
		REPD(j, 4) SendA(BIT(d, j));
		REPD(j, d) SendA(BIT(i, j));
		cnt_s = 4 + d;
		pl = l; 
		pr = r; 
		px = l + r >> 1; 
		py = px + 1;
		pm = 0;
		r = r - l - 2;
		l = 1;
		p = 0;
		phase = false;
		num_pop.assign(1, 0);
	}
}

void ReceiveA(bool x) {
	++cnt_r;
	if (!phase) {
		int sz = __lg(px - pl) + 1;
		pm = pm << 1 | x;
		if (cnt_r == sz) {
			pm += pl;
			int m = l + r >> 1;
			int qm = pm + m + 1;
			if (pm <= L && R <= qm) {
				SendA(1);
				r = m - 1;
				pl = pm; pr = qm;
			} else {
				SendA(0);
				l = m + 1;
				px = pm; py = qm;
			}
			cnt_r = 0;
			pm = 0;
			if (l > r || ++cnt_s == 18) {
				phase = true;
				cnt_r = 0;
			}
		}
	} else {
		if (py - px > 1) {
			int sz = __lg(py - px - 1) + 1;
			if (cnt_r <= sz) {
				p = p << 1 | x;
				return;
			}
		}
		if (!x) ++num_pop.back();
		else num_pop.push_back(0);
	}
}

int Answer() {
	if (R - L == 1) return L;
	vector <int> lst;
	FOR(i, pl, px) lst.push_back(i);
	if (px != py) {
		p += px;
		lst.push_back(p);
	}
	FOR(i, py, pr) lst.push_back(i);
	vector <int> st;
	REP(i, lst.size()) if (lst[i] < R) {
		while (num_pop[i]--) st.pop_back();
		st.push_back(lst[i]);
	}
	for (int x: st) if (x >= L) return x;
	return -1;
}

/*************************************
*    author: marvinthang             *
*    created: 16.03.2024 15:48:57    *
*************************************/

#include "Bruno.h"
#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i-- > 0; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

// end of template
namespace {
	int N;
	vector <int> P;
	int d, cnt_r, l, r, tl, tr;
	vector <int> pos;
}

void InitB(int n, vector <int> p) {
	N = n; P = p;
	d = 0; l = 0; r = N;
	pos.clear();
}

void ReceiveB(bool y) {
	++cnt_r;
	if (cnt_r <= 4) d = d << 1 | y;
	else if (cnt_r <= d + 4) (y ? l : r) = l + r >> 1;
	if (cnt_r < d + 4) return;
	if (cnt_r == d + 4) {
		int m = l + r >> 1;
		pos.push_back(m);
		int x = m - 1, y = m + 1;
		while (x >= l || y < r) {
			if (y == r || (x >= l && P[x] > P[y])) pos.push_back(x--);
			else pos.push_back(x + 1), ++y;
		}
		tl = 1, tr = r - l - 2;
	} else {
		int tm = tl + tr >> 1;
		if (y) tr = tm - 1;
		else tl = tm + 1;
	}
	if (cnt_r < 18 && tl <= tr) {
		int tm = tl + tr >> 1;
		int sz = __lg(pos[tl - 1] - pos[tr + 1]) + 1;
		int v = pos[tm] - pos[tr + 1];
		REPD(i, sz) SendB(BIT(v, i));
	} else {
		--tl; ++tr;
		int p = -1;
		FORE(i, pos[tl], pos[tl] + tl) if (p == -1 || P[p] > P[i]) p = i;
		if (tl) {
			int sz = __lg(tl) + 1;
			REPD(i, sz) SendB(BIT(p - pos[tl], i));
		}
		vector <int> lst;
		FOR(i, pos[tr], pos[tl]) lst.push_back(i);
		if (p != -1) lst.push_back(p);
		FORE(i, pos[tl] + tl + 1, pos[tr] + tr) lst.push_back(i);
		stack <int> st;
		for (int i: lst) {
			while (!st.empty() && P[i] < st.top()) {
				SendB(0);
				st.pop();
			}
			st.push(P[i]);
			SendB(1);
		}
	}
}

Compilation message

Anna.cpp: In function 'void InitA(int, int, int)':
Anna.cpp:61:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |    int m = l + r >> 1;
      |            ~~^~~
Anna.cpp:72:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |   px = l + r >> 1;
      |        ~~^~~
Anna.cpp: In function 'void ReceiveA(bool)':
Anna.cpp:90:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |    int m = l + r >> 1;
      |            ~~^~~

Bruno.cpp: In function 'void ReceiveB(bool)':
Bruno.cpp:61:43: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |  else if (cnt_r <= d + 4) (y ? l : r) = l + r >> 1;
      |                                         ~~^~~
Bruno.cpp:64:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |   int m = l + r >> 1;
      |           ~~^~~
Bruno.cpp:73:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
Bruno.cpp:78:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |   int tm = tl + tr >> 1;
      |            ~~~^~~~

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	0 ms	664 KB	Output is correct
4	Correct	1 ms	664 KB	Output is correct
5	Correct	0 ms	664 KB	Output is correct
6	Correct	2 ms	920 KB	Output is correct
7	Correct	1 ms	664 KB	Output is correct
8	Correct	2 ms	664 KB	Output is correct
9	Correct	2 ms	832 KB	Output is correct
10	Correct	0 ms	664 KB	Output is correct
11	Correct	1 ms	664 KB	Output is correct
12	Correct	2 ms	664 KB	Output is correct
13	Correct	1 ms	664 KB	Output is correct
14	Correct	1 ms	664 KB	Output is correct
15	Correct	0 ms	920 KB	Output is correct
16	Correct	0 ms	664 KB	Output is correct
17	Correct	2 ms	664 KB	Output is correct
18	Correct	0 ms	664 KB	Output is correct
19	Correct	1 ms	664 KB	Output is correct
20	Correct	0 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	0 ms	664 KB	Output is correct
4	Correct	1 ms	664 KB	Output is correct
5	Correct	0 ms	664 KB	Output is correct
6	Correct	2 ms	920 KB	Output is correct
7	Correct	1 ms	664 KB	Output is correct
8	Correct	2 ms	664 KB	Output is correct
9	Correct	2 ms	832 KB	Output is correct
10	Correct	0 ms	664 KB	Output is correct
11	Correct	1 ms	664 KB	Output is correct
12	Correct	2 ms	664 KB	Output is correct
13	Correct	1 ms	664 KB	Output is correct
14	Correct	1 ms	664 KB	Output is correct
15	Correct	0 ms	920 KB	Output is correct
16	Correct	0 ms	664 KB	Output is correct
17	Correct	2 ms	664 KB	Output is correct
18	Correct	0 ms	664 KB	Output is correct
19	Correct	1 ms	664 KB	Output is correct
20	Correct	0 ms	664 KB	Output is correct
21	Correct	1 ms	944 KB	Output is correct
22	Correct	2 ms	892 KB	Output is correct
23	Correct	1 ms	952 KB	Output is correct
24	Correct	1 ms	896 KB	Output is correct
25	Correct	1 ms	872 KB	Output is correct
26	Correct	2 ms	1176 KB	Output is correct
27	Correct	2 ms	896 KB	Output is correct
28	Correct	1 ms	948 KB	Output is correct
29	Correct	3 ms	948 KB	Output is correct
30	Correct	1 ms	868 KB	Output is correct
31	Correct	2 ms	892 KB	Output is correct
32	Correct	1 ms	892 KB	Output is correct
33	Correct	2 ms	868 KB	Output is correct
34	Correct	2 ms	876 KB	Output is correct
35	Correct	2 ms	920 KB	Output is correct
36	Correct	3 ms	872 KB	Output is correct
37	Correct	2 ms	920 KB	Output is correct

Subtask #3
90.0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	88 ms	16612 KB	Output is correct
2	Correct	96 ms	12408 KB	Output is correct
3	Correct	86 ms	12736 KB	Output is correct
4	Correct	94 ms	16432 KB	Output is correct
5	Correct	83 ms	16616 KB	Output is correct
6	Correct	98 ms	16616 KB	Output is correct
7	Correct	91 ms	12412 KB	Output is correct
8	Correct	106 ms	12588 KB	Output is correct
9	Correct	97 ms	12428 KB	Output is correct
10	Correct	77 ms	12584 KB	Output is correct
11	Correct	89 ms	16448 KB	Output is correct
12	Correct	76 ms	12600 KB	Output is correct
13	Correct	78 ms	12408 KB	Output is correct
14	Correct	82 ms	12420 KB	Output is correct
15	Correct	79 ms	12404 KB	Output is correct
16	Correct	91 ms	12784 KB	Output is correct
17	Correct	84 ms	12508 KB	Output is correct
18	Correct	78 ms	12588 KB	Output is correct
19	Correct	84 ms	12584 KB	Output is correct
20	Correct	82 ms	12400 KB	Output is correct
21	Correct	95 ms	12588 KB	Output is correct
22	Correct	84 ms	12408 KB	Output is correct
23	Correct	86 ms	12404 KB	Output is correct
24	Correct	81 ms	12588 KB	Output is correct
25	Correct	83 ms	12404 KB	Output is correct
26	Correct	81 ms	12416 KB	Output is correct
27	Correct	90 ms	12400 KB	Output is correct
28	Correct	86 ms	12592 KB	Output is correct
29	Correct	77 ms	12404 KB	Output is correct
30	Correct	77 ms	12396 KB	Output is correct

Submission #947512

Compilation message

Subtask #1 1.0 / 1.0

Subtask #2 9.0 / 9.0

Subtask #3 90.0 / 90.0

Subtask #1
1.0 / 1.0

Subtask #2
9.0 / 9.0

Subtask #3
90.0 / 90.0