| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1294743 | NValchanov | Ancient Machine (JOI21_ancient_machine) | C++20 | 0 ms | 0 KiB |
#include "Anna.h"
#include <vector>
#include <stack>
#include <algorithm>
#include <cassert>
#include <iostream>
using namespace std;
typedef unsigned long long ulong;
const int MAXN = 1e5 + 10;
const int BLOCK_SIZE = 63;
const int MAXLOG = 17;
const int MAXBITS = 44;
namespace {
ulong f[BLOCK_SIZE + 2 + 1];
ulong encode(vector < bool > v)
{
reverse(v.begin(), v.end());
ulong result = 0;
for(int i = 0; i < BLOCK_SIZE; i++)
{
if(v[i])
result += f[i];
}
return result;
}
void fill_f()
{
f[0] = 1;
f[1] = 1;
for(int i = 2; i <= BLOCK_SIZE + 2; i++)
{
f[i] = f[i - 1] + f[i - 2];
}
}
}
void Anna(int n, vector<char> s)
{
fill_f();
int first = -1;
vector < bool > v;
for(int i = 0; i < n; i++)
{
if(s[i] == 'X')
{
if(first == -1)
{
v.push_back(1);
first = i;
}
else
{
v.push_back(0);
}
}
else if(s[i] == 'Y')
{
v.push_back(0);
}
else if(s[i] == 'Z')
{
if(first != -1)
{
if(s[i - 1] == 'Z')
{
v.push_back(0);
}
else
{
v.push_back(1);
}
}
else
{
v.push_back(0);
}
}
}
if(first == -1)
{
Send(0);
return;
}
assert(v.size() == n);
while(v.size() % BLOCK_SIZE != 0)
{
v.push_back(0);
}
int sz = v.size();
for(int i = 0; i < sz; i += BLOCK_SIZE)
{
vector < bool > tmp;
for(int j = 0; j < BLOCK_SIZE; j++)
{
tmp.push_back(v[i + j]);
}
ulong type = encode(tmp);
for(int j = 0; j < MAXBITS; j++)
{
if(type & (1LL << j))
{
Send(1);
}
else
{
Send(0);
}
}
}
}
#include "Bruno.h"
#include <vector>
#include <algorithm>
#include <stack>
#include <iostream>
using namespace std;
typedef unsigned long long ulong;
const int MAXN = 1e5 + 10;
const int BLOCK_SIZE = 63;
const int MAXLOG = 17;
const int MAXBITS = 44;
namespace {
vector < int > red;
ulong f[BLOCK_SIZE + 2 + 1];
void fill_f()
{
f[0] = 1;
f[1] = 1;
for(int i = 2; i <= BLOCK_SIZE + 2; i++)
{
f[i] = f[i - 1] + f[i - 2];
}
}
vector < bool > decode(ulong x)
{
vector < bool > result;
for(int i = BLOCK_SIZE - 1; i >= 0; i--)
{
if(x >= f[i])
{
x -= f[i];
result.push_back(1);
}
else
{
result.push_back(0);
}
}
return result;
}
}
void Bruno(int n, int l, vector < int > a)
{
if(l == 1)
{
for(int i = 0; i < n; i++)
{
Remove(i);
}
return;
}
fill_f();
vector < bool > red;
for(int i = 0; i < l; i += MAXBITS)
{
ulong type = 0;
for(int j = 0; j < MAXBITS; j++)
{
if(a[i + j])
{
type += (1LL << j);
}
}
vector < bool > tmp = decode(type);
for(bool b : tmp)
{
red.push_back(b);
}
}
int ptr = 0;
while(ptr < n && red[ptr] == 0)
{
Remove(ptr);
ptr++;
}
int firstx = ptr;
int last = firstx;
ptr++;
while(ptr < n)
{
if(red[ptr])
{
for(int i = ptr - 1; i > last; i--)
{
Remove(i);
}
Remove(ptr);
last = ptr;
}
ptr++;
}
for(int i = last + 1; i < n; i++)
{
Remove(i);
}
if(firstx < n)
Remove(firstx);
}