#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;
#define sz(v) ((int)v.size())
#define pb push_back
#define pry cout << "YES\n"
#define prn cout << "NO\n"
#define endl '\n'
#define fst first
#define scn second
#define clear for (i = 0; i < B; ++i) { v[i] = 0; }
/* #define ONPC */
const int D = 99; // del extra
const int L = 98; // last bit
const int S = 97; // for sum
const int N = 96; // min
const int X = 95; // max
const int F = 94; // diff
const int T = 93; // temporary
const int B = 2000;
const int M = 100;
vector<bitset<B>> r(M);
void append_move(int t, int y);
void append_store(int t, vector<bool> v);
void append_and(int t, int x, int y);
void append_or(int t, int x, int y);
void append_xor(int t, int x, int y);
void append_not(int t, int x);
void append_left(int t, int x, int p);
void append_right(int t, int x, int p);
void append_add(int t, int x, int y);
void
fminmax(int a, int b, int k, bool onlymin)
{
append_not(F, b);
append_and(F ,F, D);
append_add(F ,F, a);
append_and(F ,F, L);
int s = 0;
for (int j = 0; j < B; ++j) {
if ((1<<(j+1))-1 > k) break;
s = (1<<(j+1))-1;
append_right(N, F, (1<<j));
append_or(F,F,N);
}
if (s < k) {
append_right(T, F, k-s);
append_or(F,F,T);
}
if (onlymin) {
append_and(0, F, b);
append_not(F,F);
append_and(T, F, a);
append_or(0, 0, T);
} else {
append_and(X, F, a);
append_and(N, F, b);
append_xor(T, X, a);
append_xor(F, N, b);
append_or(N, N, T);
append_or(X, X, F);
}
return;
}
int
domin(int n, int k)
{
int i, j, l, lastbit;
vector<bool> v(B, 0);
lastbit = 31-__builtin_clz(n);
for (i = n * k; i < B; ++i) v[i] = 1;
if (n != (1<<lastbit)) {
append_store(3,v);
append_or(0,0,3);
n = (1<<(1+lastbit));
}
clear;
for (i = 0; i < n; ++i) {
if (i&1) continue;
for (j = 0; j < k; ++j) v[i*k+j] = 1;
}
append_store(D,v); clear;
for (i = 0; i < n; ++i) {
if (i&1) continue;
v[i*k+k] = 1;
}
append_store(L,v); clear;
int diff = k;
int s = 0;
while (n > 1) {
append_and(1, s, D);
append_right(2, s, diff);
fminmax(1,2,k, 1);
diff <<= 1;
n >>= 1;
}
return 0;
}
void
construct_instructions(int s, int n, int k, int q)
{
int i, j, l;
assert(!s);
if (!s) {
domin(n,k);
return;
}
vector<bool> v(B, 0);
for (i = n * k; i < B; ++i) v[i] = 1;
append_store(3,v);
clear;
for (i = 0; i < n; ++i) {
if (i&1) continue;
for (j = 0; j < k; ++j) v[i*k+j] = 1;
}
append_store(D,v); clear;
for (i = 0; i < n; ++i) {
if (i&1) continue;
v[i*k+k] = 1;
}
append_store(L,v); clear;
if (n&1) {
++n;
append_or(0,0,3);
}
/* for (i = 0; i < n; ++i) { */
/* if (i&1) continue; */
/* v[i*k] = 1; */
/* } */
/* append_store(S,v); clear; */
append_and(1, 0, D);
append_right(2, 0, k);
append_and(2, 2, D);
fminmax(1,2,k,0);
append_move(0,N);
return;
}
#ifdef ONPC
int op = 0;
void append_move(int t, int y){
++op;
r[t] = r[y];
}
void append_store(int t, vector<bool> v){
++op;
for (int i = 0; i < B; ++i) r[t][i] = v[i];
}
void append_and(int t, int x, int y){
++op;
r[t] = (r[x]&r[y]);
}
void append_or(int t, int x, int y){
++op;
r[t] = (r[x]|r[y]);
}
void append_xor(int t, int x, int y){
++op;
r[t] = (r[x]^r[y]);
}
void append_not(int t, int x){
++op;
r[t] = (~r[x]);
}
void append_left(int t, int x, int p){
++op;
r[t] = (r[x]<<p);
}
void append_right(int t, int x, int p){
++op;
r[t] = (r[x]>>p);
}
void append_add(int t, int x, int y){
++op;
bitset<B> tmp;
bool ex = 0;
int cnt;
for (int i = 0; i < B; ++i) {
tmp[i] = (r[x][i]^r[y][i]^ex);
cnt = 0;
if (r[x][i]) ++cnt;
if (r[y][i]) ++cnt;
if (ex) ++cnt;
ex = (cnt > 1);
}
r[t] = tmp;
}
void
solve()
{
for (int i = 0; i < M; ++i) {
for (int j = 0; j < B; ++j) {
r[i][j] = 0;
}
}
int n, k, x, rans;
rans = inf;
cin >> n >> k;
for (int i = 0; i < n; ++i) {
cin >> x;
rans = min(x,rans);
for (int j = 0; j < k; ++j)
if ((x>>j)&1) r[0][i*k+j] = 1;
}
construct_instructions(0,n,k,100);
int ans = 0;
for (int i = 0; i < k; ++i) {
if (r[0][i]) ans |= (1<<i);
}
cout << rans << ' ' << ans << ' ' << op << endl;
}
int32_t
main(int argc, char **argv)
{
if (argc >= 2) {
freopen(argv[1], "r", stdin);
} else
ios_base::sync_with_stdio(0);cin.tie(0);
int t = 1;
/* cin >> t; */
while(t--)
solve();
}
#endif
Compilation message
registers.cpp: In function 'int domin(int, int)':
registers.cpp:85:15: warning: unused variable 'l' [-Wunused-variable]
85 | int i, j, l, lastbit;
| ^
registers.cpp: In function 'void construct_instructions(int, int, int, int)':
registers.cpp:133:15: warning: unused variable 'l' [-Wunused-variable]
133 | int i, j, l;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
320 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
324 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
320 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
