| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 752731 | 2023-06-03T14:07:37 Z | the_programmer_of_python | Painting Walls (APIO20_paint) | C++11 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
#define _us using
#define _tp template
#define _tn typename
#define _ot cout <<
#define _er cerr <<
#define _in cin >>
#define _p << ' ' <<
#define _nl '\n'
#define _el << _nl
#define _rg(i, s, e) for (auto i = s; i < e; ++i)
#define _up(i, e) _rg(i, 0, e)
#define _ce constexpr
#define _cs const
#define _st static
#define _il inline
_us ll = long long;
_tp<_tn _t> _us vec = vector<_t>;
_tp<_tn _t> _us dbl = pair<_t, _t>;
_us sz = size_t;
_us u32 = uint32_t;
#define _mp make_pair
#define _mt make_tuple
#define _f first
#define _s second
struct Vm {
_st _ce sz max_mem = 100*1000;
_st _ce int max_threads = 50*1000;
_st _ce int max_alphabet = 100*1000;
sz mem_size;
int threads;
int symbol_max;
//int mem[max_mem];
int *_cs mem;
bool active[max_mem];
//int symbols_count[50*1000];
int *_cs symbols_count;
//int *symbols[50*1000];
int *_cs*_cs symbols;
inline bool is_valid(int thread, int ptr) {
assert(0 <= thread && thread < this->threads);
assert(0 <= ptr && ptr < this->mem_size);
_cs int symbol = this->mem[ptr];
_cs int n_valid = this->symbols_count[thread];
_cs int *_cs valid = this->symbols[thread];
_up(i, n_valid) {
if (symbol == valid[i]) return true;
}
return false;
}
bool advance(int x, int y) {
assert(0 <= x && x < this->threads);
assert(0 <= y && y <= this->mem_size - this->threads);
bool res = false;
_rg(l, 0, this->threads) {
_cs int thread = (x+l)%this->threads;
if (this->is_valid(thread, y+l)) {
res = true;
active[y+l] = true;
}
}
return res;
}
};
int minimumInstructions(int N, int M, int K, int *C, int *A, int **B) {
Vm vm{.mem_size = (sz)N, .symbol_max = M, .mem = C, .symbols_count = A, .symbols = B};
memset(vm.active, 0, sizeof(vm.active));
return -1;
}
/*|------------------------------------------------------------------------|*\
|*| Spec: |*|
|*| Start with the following parameters: |*|
|*| N -- mem size |*|
|*| M -- threads |*|
|*| K -- symbol count |*|
|*| C -- mem values |*|
|*| A -- # of valid symbols per thread |*|
|*| B -- valid symbols of each thread |*|
|*| Return: Minimum # of instructions to activate entire memory, or -1 |*|
|*| INSR(x, y) == |*|
|*| x -- 0..<M |*|
|*| y -- 0..(N-M) |*|
|*| For all l in 0..<M |*|
|*| Use thread ((x + l) % M) |*|
|*| If C[y+l] is a valid symbol, activate it |*|
\*|------------------------------------------------------------------------|*/