/*
* NOTES
*
* - posso fare una funzione AND/OR per fare l'AND/OR di tutti i bit di un registro
* (ANDify, ORify)
* - posso costruire il ternario:
* // t = a if x, b otherwise
* CHOOSE(t, a, b, x): // t : final register, a b : fattori, x = bool
* ORify(i = st--, x)
* NOT(j = st--, i)
* AND(k = st--, i, a)
* AND(l = st--, j, b)
* ADD(t, k, l)
* st += 4
* - posso costruire un bool(a > b) ?
* idea: farlo bit a bit
* if msb(a) == 1 && msb(b) == 0:
* ans = 1
* set(b, null)
*/
#include "registers.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int M = 100;
constexpr int B = 2000;
int st = M - 1;
struct id {
int i;
id() : i(st--) {}
~id() { ++st; }
};
int n, k;
int id_zero = st--;
int id_one = st--;
vector<bool> zero(B);
vector<bool> one(B);
// if (r[a] is NULL) r[t] is set to 0
// else r[t] is set to 1
void MAKEBOOL(int t, int a) {
id shifted;
append_move(t, a);
int shift = 1;
for (; shift < B; shift <<= 1) {
append_left(shifted.i, t, shift);
append_or(t, t, shifted.i);
append_right(shifted.i, t, shift);
append_or(t, t, shifted.i);
}
append_left(shifted.i, t, B / 2);
append_or(t, t, shifted.i);
append_right(shifted.i, t, B / 2);
append_or(t, t, shifted.i);
}
// if (r[x] is NULL) r[t] = r[b]
// else r[t] = r[a]
void TERNARY(int t, int a, int b, int x) { // (t, if_true, if_false, bool)
assert(a != b);
id mask, f1, f2;
MAKEBOOL(mask.i, x); // not always necessary
append_and(f1.i, mask.i, a);
append_not(mask.i, mask.i);
append_and(f2.i, mask.i, b);
append_add(t, f1.i, f2.i);
}
void EXTRACT_SUBSEGMENT(int t, int a, int l, int r) {
append_move(t, a);
append_left(t, t, B-1-r);
append_right(t, t, B-1-r+l);
}
void GET_BIT(int t, int a, int i) {
EXTRACT_SUBSEGMENT(t, a, i, i);
}
// r[t] becomes bool(a < b)
void LESS(int t, int a, int b) {
assert(a != b);
append_store(t, zero);
id oa, ob;
append_move(oa.i, a);
append_move(ob.i, b);
id ta, tb;
for (int i = k-1; i >= 0; --i) {
GET_BIT(ta.i, oa.i, i);
GET_BIT(tb.i, oa.i, i);
// if r[a][0] & !r[b][0]:
// set r[a] to 0 else r[a]
// set ans to 0 else ans
//
// ... same con r[b][0] & !r[a]
id tnot, tand;
append_not(tnot.i, ta.i);
append_and(tand.i, tnot.i, tb.i);
TERNARY(t, id_one, t, tand.i);
TERNARY(oa.i, id_zero, oa.i, tand.i);
append_not(tnot.i, tb.i);
append_and(tand.i, ta.i, tnot.i);
TERNARY(t, id_zero, t, tand.i);
TERNARY(ob.i, id_zero, ob.i, tand.i);
}
}
// r[t] becomes the i-th integer in r[0]
void GET_INPUT(int t, int i) {
EXTRACT_SUBSEGMENT(t, 0, k*i, k*i+k-1);
}
// r[t] stores min(r[a], r[b])
void MIN(int t, int a, int b) {
id comp;
LESS(comp.i, a, b);
TERNARY(t, a, b, comp.i);
}
void construct_instructions(int s, int n, int k, int q) {
::n = n, ::k = k;
assert(s == 0); // so far, only find minimum
for (int i = 0; i < B; ++i) { one[i] = 1; }
append_store(id_one, one);
append_store(id_zero, zero);
// actual code
id ans;
append_store(ans.i, one);
for (int i = 0; i < n; ++i) {
id cur;
GET_INPUT(cur.i, i);
MIN(ans.i, ans.i, cur.i);
}
append_move(0, ans.i);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Wrong answer detected in grader |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Wrong answer detected in grader |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
588 KB |
Incorrect min value |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Wrong answer detected in grader |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
