Submission #1309115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309115		minh30082008	Ancient Machine (JOI21_ancient_machine)	C++20	0 / 100	33 ms	6308 KiB

Anna

#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
static ull fA[100];


void Anna(int n, vector<char> S) {
// Fibonacci starting 1,2,3,5,... (Zeckendorf-compatible)
fA[0] = 1;
fA[1] = 2;
for (int i = 2; i < 90; ++i) fA[i] = fA[i-1] + fA[i-2];


// build vv as in your original idea
vector<int> vv;
int vt = -1;
for (int i = 0; i < n; ++i) if (S[i] == 'X') { vt = i; break; }


if (vt == -1) {
vv.assign(n, 0);
} else {
for (int i = 0; i < vt; ++i) vv.push_back(0);
vv.push_back(1);
if (vt + 1 < n) vv.push_back(0);
for (int i = vt + 2; i < n; ++i)
vv.push_back( (S[i] == 'Z' && S[i-1] != 'Z') ? 1 : 0 );
}


// send blocks of up to 64 positions (r-l+1 <= 64)
int l = 0;
while (l < n) {
int r = min(l + 63, n - 1);
int m = r - l + 1;
// compute encoded value
unsigned long long res = 0ULL;
for (int i = l; i <= r; ++i) if (vv[i]) res += fA[i - l];


// determine number of bits needed to represent values up to sum_{0..m-1} f[i]
// conservative threshold: f[m+1] (we need 2^bits >= f[m+1])
unsigned __int128 threshold = (unsigned __int128)fA[m + 1];
unsigned __int128 pow2 = 1;
int bits = 0;
while (pow2 < threshold) { pow2 <<= 1; ++bits; }


// send LSB-first
for (int i = 0; i < bits; ++i) {
Send( (int)((res >> i) & 1ULL) );
}


l = r + 1;
}
}

Bruno

#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;
using ull2 = unsigned long long;
static ull2 fB[100];


void Bruno(int n, int L, vector<int> A) {
// build same Fibonacci
fB[0] = 1;
fB[1] = 2;
for (int i = 2; i < 90; ++i) fB[i] = fB[i-1] + fB[i-2];


int l = 0;
int d = 0; // index into A
vector<int> s1; // decoded bits


while (l < n) {
int r = min(l + 63, n - 1);
int m = r - l + 1;


// compute bits used by Anna for this block (same rule)
unsigned __int128 threshold = (unsigned __int128)fB[m + 1];
unsigned __int128 pow2 = 1;
int bits = 0;
while (pow2 < threshold) { pow2 <<= 1; ++bits; }


// read bits (LSB-first)
unsigned long long res = 0ULL;
for (int i = 0; i < bits; ++i) {
if (d + i < L && A[d + i]) {
res |= (1ULL << i);
}
}
d += bits;


// convert res to fibonacci-bit vector of length m
vector<int> tmp;
for (int i = m - 1; i >= 0; --i) {
if (res >= fB[i]) {
res -= fB[i];
tmp.push_back(1);
} else tmp.push_back(0);
}
reverse(tmp.begin(), tmp.end());
s1.insert(s1.end(), tmp.begin(), tmp.end());


l = r + 1;
}


// safety: pad s1 if shorter
if ((int)s1.size() < n) s1.resize(n, 0);


// find first 1 (vt)
int vt = n;
for (int i = 0; i < n; ++i) if (s1[i]) { vt = i; break; }


// if no 1s, just remove all devices from left to right
if (vt == n) {
for (int i = 0; i < n; ++i) Remove(i);
return;
}


// remove indices before vt (left of first 1)
for (int i = 0; i < vt; ++i) Remove(i);


// now process the rest
vector<int> vv;
vv.push_back(vt);
for (int i = vt + 1; i < n; ++i) {
if (s1[i] == 1) {
// collapse current stack vv until only one left
while (vv.size() > 1) {
Remove(vv.back());
vv.pop_back();
}
// remove i
Remove(i);
} else {
vv.push_back(i);
}
}
// remove remaining in vv
for (int x : vv) Remove(x);
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 95