Submission #931176

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
931176	2024-02-21T10:40:36 Z	boris_mihov	Ancient Machine (JOI21_ancient_machine)	C++17	5 / 100	40 ms	8156 KB

Anna

#include "Anna.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#include <vector>

typedef long long llong;
const int BUCKET_SIZE = 73;
const int MYLOG = 51;

llong fib[BUCKET_SIZE + 5];
struct FibbonacciConverter
{
    std::string getString(std::string s)
    {
        while (s.size() % BUCKET_SIZE != 0)
        {
            s += '0';
        }

        // std::cout << "send: " << s << '\n';
        std::string res;
        for (int i = 0 ; i < s.size() ; i += BUCKET_SIZE)
        {
            llong currNum = 0;
            for (int j = i ; j < i + BUCKET_SIZE ; ++j)
            {
                if (j != i) assert(s[j] == '0' || s[j - 1] == '0');
                if (s[j] == '1') currNum += fib[j - i];
                assert(currNum < (1LL << MYLOG));
            }

            // std::cout << "num is: " << currNum << '\n';
            for (int log = MYLOG - 1 ; log >= 0 ; --log)
            {
                if (currNum & (1LL << log))
                {
                    res += '1';
                } else
                {
                    res += '0';
                }
            }
        }

        return res;
    }

    std::string fromString(std::string s)
    {
        assert(s.size() % MYLOG == 0);
        std::string res;
        for (int i = 0 ; i < s.size() ; i += MYLOG)
        {
            llong currNum = 0;
            for (int j = i ; j < i + MYLOG ; ++j)
            {
                currNum *= 2;
                if (s[j])
                {
                    currNum++;
                }
            }

            std::string toAdd;
            for (int pos = BUCKET_SIZE ; pos > 0 ; --pos)
            {
                if (currNum >= fib[pos - 1])
                {
                    toAdd += '1';
                    currNum -= fib[pos - 1];
                } else
                {
                    toAdd += '0';
                }
            }

            std::reverse(toAdd.begin(), toAdd.end());
            res += toAdd;
        }

        return res;
    }
};

void Anna(int N, std::vector <char> s) 
{
    fib[0] = 1;
    fib[1] = 2;
    for (int i = 2 ; i < BUCKET_SIZE + 5 ; ++i)
    {
        fib[i] = fib[i - 1] + fib[i - 2];
    }

    bool foundX = false;
    bool shouldSend = false;
    std::string res;
    for (int i = 0 ; i < N ; ++i)
    {
        if (!foundX && s[i] == 'X')
        {
            foundX = true;
            res += '1';
            shouldSend = false;
        } else if (foundX && s[i] == 'Z' && res.back() == '0' && (shouldSend || i + 1 == N || s[i + 1] != 'Z'))
        {
            res += '1';
            shouldSend = false;
        } else
        {
            res += '0';
            shouldSend = false;
        }
    }

    // std::cout << "Res before: " << res << '\n';
    FibbonacciConverter converter;
    res = converter.getString(res);

    // std::cout << "res: " << res.size() << '\n';
    for (int i = 0 ; i < res.size() ; ++i)
    {
        Send(res[i] - '0');
    }
}

Bruno

#include "Bruno.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 100000 + 10;
const int BUCKET_SIZE = 73;
const int MYLOG = 51;

llong fibB[BUCKET_SIZE + 5];
struct FibbonacciConverterB
{
    std::string getString(std::string s)
    {
        while (s.size() % BUCKET_SIZE != 0)
        {
            s += '0';
        }

        std::string res;
        for (int i = 0 ; i < s.size() ; i += BUCKET_SIZE)
        {
            llong currNum = 0;
            for (int j = i ; j < i + BUCKET_SIZE ; ++j)
            {
                if (s[j] == '1') currNum += fibB[j - i];
            }

            assert(currNum < (1LL << MYLOG));
            for (int log = MYLOG - 1 ; log >= 0 ; --log)
            {
                if (currNum & (1LL << log))
                {
                    res += '1';
                } else
                {
                    res += '0';
                }
            }
        }

        return res;
    }

    std::string fromString(std::string s)
    {
        assert(s.size() % MYLOG == 0);
        std::string res;
        for (int i = 0 ; i < s.size() ; i += MYLOG)
        {
            llong currNum = 0;
            for (int j = i ; j < i + MYLOG ; ++j)
            {
                currNum *= 2;
                if (s[j] == '1')
                {
                    currNum++;
                }
            }

            // std::cout << "curr num is: " << currNum << '\n';
            std::string toAdd;
            for (int pos = BUCKET_SIZE ; pos > 0 ; --pos)
            {
                if (currNum >= fibB[pos - 1])
                {
                    toAdd += '1';
                    currNum -= fibB[pos - 1];
                } else
                {
                    toAdd += '0';
                }
            }

            std::reverse(toAdd.begin(), toAdd.end());
            res += toAdd;
        }

        return res;
    }
};

void Bruno(int N, int L, std::vector <int> A) 
{
    fibB[0] = 1;
    fibB[1] = 2;
    for (int i = 2 ; i < BUCKET_SIZE + 5 ; ++i)
    {
        fibB[i] = fibB[i - 1] + fibB[i - 2];
    }

    std::string res;
    for (int i = 0 ; i < L ; ++i)
    {
        res += '0' + A[i];
    }

    FibbonacciConverterB converter;
    std::string s = converter.fromString(res);
    
    // std::cout << "receive: " << s << '\n';
    int xPos = -1;
    int added = 0;
    std::vector <int> pos;
    for (int i = 0 ; i < L ; ++i)
    {
        if (s[i] == '1')
        {
            if (xPos == -1) xPos = i;
            // std::cout << "here: " << i << '\n';
            pos.push_back(i);
        }
    }

    if (pos.empty())
    {
        for (int i = 0 ; i < N ; ++i)
        {
            Remove(i);
        }

        return;
    }

    if (pos.back() < N - 1) pos.push_back(N - 1);
    for (int i = 0 ; i < xPos ; ++i)
    {
        Remove(i);
    }

    for (int i = 1 ; i < pos.size() ; ++i)
    {
        for (int j = pos[i] - 1 ; j > pos[i - 1] ; --j)
        {
            Remove(j);
        }

        Remove(pos[i]);
    }

    Remove(pos[0]);
}

Compilation message

Anna.cpp: In member function 'std::string FibbonacciConverter::getString(std::string)':
Anna.cpp:23:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for (int i = 0 ; i < s.size() ; i += BUCKET_SIZE)
      |                          ~~^~~~~~~~~~
Anna.cpp: In member function 'std::string FibbonacciConverter::fromString(std::string)':
Anna.cpp:53:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for (int i = 0 ; i < s.size() ; i += MYLOG)
      |                          ~~^~~~~~~~~~
Anna.cpp: In function 'void Anna(int, std::vector<char>)':
Anna.cpp:121:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     for (int i = 0 ; i < res.size() ; ++i)
      |                      ~~^~~~~~~~~~~~

Bruno.cpp: In member function 'std::string FibbonacciConverterB::getString(std::string)':
Bruno.cpp:23:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for (int i = 0 ; i < s.size() ; i += BUCKET_SIZE)
      |                          ~~^~~~~~~~~~
Bruno.cpp: In member function 'std::string FibbonacciConverterB::fromString(std::string)':
Bruno.cpp:51:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for (int i = 0 ; i < s.size() ; i += MYLOG)
      |                          ~~^~~~~~~~~~
Bruno.cpp: In function 'void Bruno(int, int, std::vector<int>)':
Bruno.cpp:133:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     for (int i = 1 ; i < pos.size() ; ++i)
      |                      ~~^~~~~~~~~~~~
Bruno.cpp:105:9: warning: unused variable 'added' [-Wunused-variable]
  105 |     int added = 0;
      |         ^~~~~

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	788 KB	Output is correct
2	Correct	0 ms	780 KB	Output is correct
3	Correct	0 ms	788 KB	Output is correct
4	Correct	0 ms	784 KB	Output is correct
5	Correct	0 ms	792 KB	Output is correct
6	Correct	1 ms	1000 KB	Output is correct
7	Correct	0 ms	796 KB	Output is correct
8	Correct	0 ms	788 KB	Output is correct
9	Correct	0 ms	788 KB	Output is correct
10	Correct	0 ms	784 KB	Output is correct
11	Correct	0 ms	780 KB	Output is correct

Subtask #2

0 / 95.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	40 ms	8156 KB	Wrong Answer [6]
2	Halted	0 ms	0 KB	-