Submission #1316668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316668		tvgk	Ancient Machine (JOI21_ancient_machine)	C++20	98 / 100	40 ms	6468 KiB

Anna

#include<bits/stdc++.h>
#include "Anna.h"
#include <vector>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 2e5 + 7, inf = 1e9 + 7;

static ll fibo[100];

void Anna(int n, std::vector<char> s)
{
    int stt = -1;
    vector<bool> bit;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == 'X' && stt == -1)
            stt = i;

        if (s[i] == 'Z' && bit.size())
        {
            bit.back() = 0;
            bit.push_back(1);
        }
        else
            bit.push_back(0);
    }

    stt = max(0, stt);
    for (int i = 0; i <= __lg(n); i++)
        Send((stt >> i) & 1);

    fibo[0] = 1;
    fibo[1] = 2;
    ll sum = 0;
    for (int i = 2; i <= 50; i++)
    {
        fibo[i] = fibo[i - 1] + fibo[i - 2];
        sum += fibo[i];
    }

    for (int i = 0; i < bit.size(); i += 51)
    {
        ll sum = 0;
        for (int j = 0; j < 51; j++)
        {
            if (i + j >= bit.size())
                break;

            sum += fibo[j] * bit[i + j];
        }

        for (int i = 0; i < 36; i++)
            Send((sum >> i) & 1);
    }
}

Bruno

#include "Bruno.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 2e5 + 7;

static ll fibo[mxN];

void Bruno(int n, int l, std::vector<int> a)
{
    fibo[0] = 1;
    fibo[1] = 2;
    ll sum = 0;
    for (int i = 2; i <= 50; i++)
    {
        fibo[i] = fibo[i - 1] + fibo[i - 2];
        sum += fibo[i];
    }

    string s;
    for (int i = __lg(n) + 1; i < a.size(); i += 36)
    {
        ll sum = 0;
        for (int j = 0; j < 36; j++)
            sum += (1LL * a[i + j]) << j;

        string t;
        for (int j = 50; j >= 0; j--)
        {
            if (sum >= fibo[j])
            {
                sum -= fibo[j];
                t += 'Z';
            }
            else
                t += 'Y';
        }
        reverse(t.begin(), t.end());
        s += t;
    }

    int tmp = 0;
    for (int i = 0; i <= __lg(n); i++)
        tmp += (a[i] << i);
    s[tmp] = 'X';

    stack<int> stk;
    int stt = -1;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == 'X' && stt == -1)
            stt = i;

        if (stt == -1)
        {
            Remove(i);
            continue;
        }

        if (s[i] == 'Z')
        {
            while (stk.size() > 1)
            {
                Remove(stk.top());
                stk.pop();
            }
            Remove(i);
        }
        else
            stk.push(i);
    }
    while (stk.size())
    {
        Remove(stk.top());
        stk.pop();
    }
}

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