Submission #947512

#TimeUsernameProblemLanguageResultExecution timeMemory
947512marvinthangShopping (JOI21_shopping)C++17
100 / 100
106 ms16616 KiB
/************************************* * 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 (stderr)

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;
      |            ~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...