#include "registers.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double;
using str = string;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
template<class T> using V = vector<T>;
template<class T, size_t SZ> using AR = array<T,SZ>;
template<class T> using PR = pair<T,T>;
template<class T> int lwb(V<T>& a, const T& b)
{
return int(lower_bound(begin(a), end(a),b)-begin(a));
}
const int MOD = 1e9+7;
const int MX = 2e5+5;
const ll INF = 1e18;
const db PI = acos((db)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;
constexpr int pct(int x)
{
return __builtin_popcount(x);
}
constexpr int bits(int x)
{
return x == 0 ? 0 : 31-__builtin_clz(x);
}
constexpr int p2(int x)
{
return 1<<x;
}
constexpr int msk2(int x)
{
return p2(x)-1;
}
ll cdiv(ll a, ll b)
{
return a/b+((a^b)>0&&a%b);
}
ll fdiv(ll a, ll b)
{
return a/b-((a^b)<0&&a%b);
}
template<class T> bool ckmin(T& a, const T& b)
{
return b < a ? a = b, 1 : 0;
}
template<class T> bool ckmax(T& a, const T& b)
{
return a < b ? a = b, 1 : 0;
}
template<class T, class U> T fstTrue(T lo, T hi, U first)
{
hi ++;
assert(lo <= hi);
while (lo < hi)
{
T mid = lo+(hi-lo)/2;
first(mid) ? hi = mid : lo = mid+1;
}
return lo;
}
template<class T, class U> T lstTrue(T lo, T hi, U first)
{
lo --;
assert(lo <= hi);
while (lo < hi)
{
T mid = lo+(hi-lo+1)/2;
first(mid) ? lo = mid : hi = mid-1;
}
return lo;
}
template<class T> void remDup(vector<T>& v)
{
sort(begin(v), end(v));
v.erase(unique(begin(v), end(v)),end(v));
}
template<class T, class U> void erase(T& t, const U& u)
{
auto it = t.find(u);
assert(it != end(t));
t.erase(it);
}
inline namespace Helpers
{
template<class T, class = void> struct is_iterable : false_type {};
template<class T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),
decltype(end(declval<T>()))
>
> : true_type {};
template<class T> constexpr bool is_iterable_v = is_iterable<T>::value;
template<class T, class = void> struct is_readable : false_type {};
template<class T> struct is_readable<T,
typename std::enable_if_t<
is_same_v<decltype(cin >> declval<T&>()), istream&>
>
> : true_type {};
template<class T> constexpr bool is_readable_v = is_readable<T>::value;
template<class T, class = void> struct is_printable : false_type {};
template<class T> struct is_printable<T,
typename std::enable_if_t<
is_same_v<decltype(cout << declval<T>()), ostream&>
>
> : true_type {};
template<class T> constexpr bool is_printable_v = is_printable<T>::value;
}
inline namespace Input
{
template<class T> constexpr bool needs_input_v = !is_readable_v<T> && is_iterable_v<T>;
template<class T, class ...U> void re(T& t, U&... u);
template<class T, class U> void re(pair<T,U>& p);
template<class T> typename enable_if<is_readable_v<T>,void>::type re(T& x)
{
cin >> x;
}
template<class T> void re(complex<T>& c)
{
T a,b;
re(a,b);
c = {a,b};
}
template<class T> typename enable_if<needs_input_v<T>,void>::type re(T& i);
template<class T, class U> void re(pair<T,U>& p)
{
re(p.first,p.second);
}
template<class T> typename enable_if<needs_input_v<T>,void>::type re(T& i)
{
for (auto& x: i) re(x);
}
template<class T, class ...U> void re(T& t, U&... u)
{
re(t);
re(u...);
}
void rv(size_t) {}
template<class T, class ...U> void rv(size_t N, V<T>& t, U&... u);
template<class...U> void rv(size_t, size_t N2, U&... u);
template<class T, class ...U> void rv(size_t N, V<T>& t, U&... u)
{
t.resize(N);
re(t);
rv(N,u...);
}
template<class...U> void rv(size_t, size_t N2, U&... u)
{
rv(N2,u...);
}
void decrement() {}
template<class T, class ...U> void decrement(T& t, U&... u)
{
--t;
decrement(u...);
}
}
inline namespace ToString
{
template<class T> constexpr bool needs_output_v = !is_printable_v<T> && is_iterable_v<T>;
template<class T> typename enable_if<is_printable_v<T>,str>::type ts(T v)
{
stringstream ss;
ss << fixed << setprecision(15) << v;
return ss.str();
}
template<class T> str bit_vec(T t)
{
str res = "{";
for (int i = (0); i < (int((t).size())); ++i) res += ts(t[i]);
res += "}";
return res;
}
str ts(V<bool> v)
{
return bit_vec(v);
}
template<size_t SZ> str ts(bitset<SZ> b)
{
return bit_vec(b);
}
template<class T, class U> str ts(pair<T,U> p);
template<class T> typename enable_if<needs_output_v<T>,str>::type ts(T v);
template<class T, class U> str ts(pair<T,U> p)
{
return "("+ts(p.first)+", "+ts(p.second)+")";
}
template<class T> typename enable_if<is_iterable_v<T>,str>::type ts_sep(T v, str sep)
{
bool fst = 1;
str res = "";
for (const auto& x: v)
{
if (!fst) res += sep;
fst = 0;
res += ts(x);
}
return res;
}
template<class T> typename enable_if<needs_output_v<T>,str>::type ts(T v)
{
return "{"+ts_sep(v,", ")+"}";
}
template<int, class T> typename enable_if<!needs_output_v<T>,vs>::type
ts_lev(const T& v)
{
return {ts(v)};
}
template<int lev, class T> typename enable_if<needs_output_v<T>,vs>::type
ts_lev(const T& v)
{
if (lev == 0 || !int((v).size())) return {ts(v)};
vs res;
for (const auto& t: v)
{
if (int((res).size())) res.back() += ",";
vs tmp = ts_lev<lev-1>(t);
res.insert(end(res),begin(tmp), end(tmp));
}
for (int i = (0); i < (int((res).size())); ++i)
{
str bef = " ";
if (i == 0) bef = "{";
res[i] = bef+res[i];
}
res.back() += "}";
return res;
}
}
inline namespace Output
{
template<class T> void pr_sep(ostream& os, str, const T& t)
{
os << ts(t);
}
template<class T, class... U> void pr_sep(ostream& os, str sep, const T& t, const U&... u)
{
pr_sep(os,sep,t);
os << sep;
pr_sep(os,sep,u...);
}
template<class ...T> void pr(const T&... t)
{
pr_sep(cout,"",t...);
}
void ps()
{
cout << "\n";
}
template<class ...T> void ps(const T&... t)
{
pr_sep(cout," ",t...);
ps();
}
template<class ...T> void dbg_out(const T&... t)
{
pr_sep(cerr," | ",t...);
cerr << endl;
}
void loc_info(int line, str names)
{
cerr << "Line(" << line << ") -> [" << names << "]: ";
}
template<int lev, class T> void dbgl_out(const T& t)
{
cerr << "\n\n" << ts_sep(ts_lev<lev>(t),"\n") << "\n" << endl;
}
}
inline namespace FileIO
{
void setIn(str second)
{
freopen(second.c_str(),"r",stdin);
}
void setOut(str second)
{
freopen(second.c_str(),"w",stdout);
}
void setIO(str second = "")
{
cin.tie(0)->sync_with_stdio(0);
if (int((second).size())) setIn(second+".in"), setOut(second+".out");
}
}
void init_bits(int t, vi bits)
{
vb v(2000);
for (int i: bits) v.at(i) = 1;
append_store(t, v);
}
void op_move(int t, int x)
{
append_move(t,x);
}
void op_left(int t, int x, int second)
{
append_left(t,x,second);
}
void op_and(int t, int x, int y)
{
append_and(t,x,y);
}
void op_or(int t, int x, int y)
{
append_or(t,x,y);
}
void op_xor(int t, int x, int y)
{
append_xor(t,x,y);
}
void op_add(int t, int x, int y)
{
append_add(t,x,y);
}
void op_not(int t, int x)
{
append_not(t,x);
}
void op_right(int t, int x, int second)
{
append_right(t,x,second);
}
vi num_bits(int x)
{
vi ans;
for (int i = (0); i < (x); ++i) ans.push_back(i);
return ans;
}
void construct_instructions(int second, int n, int k, int q)
{
int p = 1;
if (second == 0)
{
while (p < n) p *= 2;
{
vi rel;
for (int i = (n); i < (p); ++i) for (int j = (0); j < (k); ++j) rel.push_back(i*k+j);
init_bits(1,rel);
op_or(0,0,1);
n = p;
}
int tot = n*k;
vi all_bits;
for (int i = (0); i < (tot); ++i) all_bits.push_back(i);
init_bits(20,all_bits);
init_bits(21, {0});
for (int len = k; len < tot; len *= 2)
{
vi a,b;
for (int i = (0); i < (tot); ++i)
{
if (i%(2*len) < len) a.push_back(i);
else b.push_back(i);
}
init_bits(1,a);
op_and(3,1,0);
op_right(4,0,len);
op_not(5,4);
op_and(5,5,1);
op_add(6,3,5);
vi rel;
for (int i = len; i < tot; i += 2*len) rel.push_back(i);
init_bits(7,rel);
op_and(6,6,7);
op_right(7,6,len);
op_not(7,7);
op_add(6,6,7);
op_add(6,6,21);
op_xor(7,6,20);
op_and(3,3,7);
op_and(4,4,6);
op_or(0,3,4);
}
}
else
{
p = n;
if (p&1) ++p;
{
vi rel;
for (int i = (n); i < (p); ++i) for (int j = (0); j < (k); ++j) rel.push_back(i*k+j);
init_bits(1,rel);
op_or(0,0,1);
n = p;
}
int tot = n*k;
vi all_bits;
for (int i = (0); i < (tot); ++i) all_bits.push_back(i);
init_bits(20,all_bits);
init_bits(21, {0});
init_bits(40,num_bits(k));
append_print(0);
for (int it = (0); it < (105); ++it)
{
auto tran = [&]()
{
int len = k;
vi a,b;
for (int i = (0); i < (tot); ++i)
{
if (i%(2*len) < len) a.push_back(i);
else b.push_back(i);
}
init_bits(1,a);
op_and(3,1,0);
op_right(4,0,len);
op_and(4,4,1);
op_not(5,4);
op_and(5,5,1);
op_add(6,3,5);
vi rel;
for (int i = len; i < tot; i += 2*len) rel.push_back(i);
init_bits(7,rel);
op_and(6,6,7);
op_right(7,6,len);
op_not(7,7);
op_add(6,6,7);
op_add(6,6,21);
op_xor(7,6,20);
op_and(12,3,7);
op_and(13,4,6);
op_or(0,12,13);
op_and(8,3,6);
op_and(9,4,7);
op_or(8,8,9);
op_left(8,8,len);
op_or(0,0,8);
};
if (it%2 == 0)
{
tran();
}
else
{
assert(n == p);
op_move(50,0);
op_and(50,50,40);
op_right(0,0,k);
{
vi rel;
for (int j = (0); j < (k); ++j) rel.push_back((n-1)*k+j);
init_bits(80,rel);
op_or(0,0,80);
}
append_print(0);
tran();
append_print(0);
op_left(0,0,k);
op_and(0,0,20);
op_or(0,0,50);
}
append_print(0);
append_print(10);
}
}
}
Compilation message
registers.cpp: In function 'void FileIO::setIn(str)':
registers.cpp:338:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
338 | freopen(second.c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
registers.cpp: In function 'void FileIO::setOut(str)':
registers.cpp:342:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
342 | freopen(second.c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
296 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1188 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1188 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1184 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1192 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1184 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1192 KB |
Output is correct |
| 6 |
Correct |
5 ms |
1192 KB |
Output is correct |
| 7 |
Correct |
5 ms |
1192 KB |
Output is correct |
