oj.uz

Submission #931365

# Submission time Handle Problem Language Result Execution time Memory
931365 2024-02-21T16:35:06 Z boris_mihov Ancient Machine (JOI21_ancient_machine) C++17
100 / 100
 46 ms 8588 KB 
#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.size() << '\n';
        std::string res;
        for (int i = 0 ; i < s.size() ; i += BUCKET_SIZE)
        {
            llong currNum = 0;
            std::string sequence;
            for (int j = i ; j < i + BUCKET_SIZE ; ++j)
            {
                sequence += s[j];
                if (j != i) assert(s[j] == '0' || s[j - 1] == '0');
                if (s[j] == '1') currNum += fib[j - i];
                assert(currNum < (1LL << MYLOG));
            }
            
            assert(currNum <= fib[BUCKET_SIZE]);
            // std::cout << "curr num is: " << sequence << '\n';
            for (int log = MYLOG - 1 ; log >= 0 ; --log)
            {
                if (currNum & (1LL << log))
                {
                    res += '1';
                } else
                {
                    res += '0';
                }
            }
        }

        // std::cout << "here: " << res << '\n';
        // std::cout << "here: " << fromString(res) << '\n';
        // std::cout << "here: " << s << '\n';
        // exit(0);

        // std::cout << "are equal: " << (fromString(res) == s) << '\n';
        // assert(fromString(res) == s);
        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::string toAdd;
            for (int pos = BUCKET_SIZE ; pos > 0 ; --pos)
            {
                if (currNum >= fib[pos - 1])
                {
                    toAdd += '1';
                    currNum -= fib[pos - 1];
                } else
                {
                    toAdd += '0';
                }
            }

            assert(currNum == 0);
            std::reverse(toAdd.begin(), toAdd.end());
            // std::cout << "curr num is: " << toAdd << '\n';
            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];
    }

    std::string res;
    bool foundX = false;
    int xPos = -2;
    bool hasZinFront = false;
    for (int i = 0 ; i < N ; ++i)
    {
        if (!foundX && s[i] == 'X')
        {
            xPos = i;
            foundX = true;
            res += '1';
            // std::cout << i << "  ";
        } else if (foundX && s[i] == 'Z' && ((res.back() == '0' && (i + 1 == N || s[i + 1] != 'Z'))))
        {
            // std::cout << i << "  ";
            res += '1';
        } else if (s[i] == 'Z' && i == xPos + 1)
        {
            res += '0';
            hasZinFront = true;
        } else
        {
            // assert(!foundX || s[i - 1] == 'X' || s[i] != 'Z' || (i + 1 < N && s[i + 1] == 'Z'));
            res += '0';
        }
    }

    // std::cout << "x pos: " << xPos << '\n'.

    // std::cout << "has z in front: " << hasZinFront << '\n';
    // std::cout << "Res before: " << res << '\n';
    // std::cout << "send: " << res <<
    FibbonacciConverter converter;
    res = converter.getString(res);

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

    Send(hasZinFront);
    // std::cout << "\n\n\n";
}

#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::cout << "send: " << s << '\n';
        std::string res;
        for (int i = 0 ; i < s.size() ; i += BUCKET_SIZE)
        {
            llong currNum = 0;
            std::string sequence;
            for (int j = i ; j < i + BUCKET_SIZE ; ++j)
            {
                sequence += s[j];
                if (j != i) assert(s[j] == '0' || s[j - 1] == '0');
                if (s[j] == '1') currNum += fibB[j - i];
                assert(currNum < (1LL << MYLOG));
            }
            
            assert(currNum <= fibB[BUCKET_SIZE]);
            // std::cout << "curr num is: " << sequence << '\n';
            for (int log = MYLOG - 1 ; log >= 0 ; --log)
            {
                if (currNum & (1LL << log))
                {
                    res += '1';
                } else
                {
                    res += '0';
                }
            }
        }

        // std::cout << "here: " << res << '\n';
        // std::cout << "here: " << fromString(res) << '\n';
        // std::cout << "here: " << s << '\n';
        // exit(0);
        assert(fromString(res) == s);
        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::string toAdd;
            for (int pos = BUCKET_SIZE ; pos > 0 ; --pos)
            {
                if (currNum >= fibB[pos - 1])
                {
                    toAdd += '1';
                    currNum -= fibB[pos - 1];
                } else
                {
                    toAdd += '0';
                }
            }

            assert(currNum == 0);
            std::reverse(toAdd.begin(), toAdd.end());
            // std::cout << "curr num is: " << toAdd << '\n';
            res += toAdd;
        }

        return res;
    }
};

void Bruno(int N, int L, std::vector <int> A) 
{
    bool hasZinFront = false;
    if (A.back() == 1) hasZinFront = true;
    A.pop_back(); L--;

    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::string s = res;

    // std::cout << "receive: " << s << '\n';
    // std::cout << "receive size: " << s.size() << '\n';
    assert(converter.getString(s) == res);
    int xPos = -1;
    int added = 0;
    std::vector <int> pos;
    for (int i = 0 ; i < N ; ++i)
    {
        if (s[i] == '1')
        {
            if (xPos == -1) 
            {
                xPos = i;
                if (hasZinFront) 
                {
                    // std::cout << "here: " << i + 1 << "  ";
                    s[i + 1] = '1';
                }
            }
            // std::cout << "here: " << i << "  ";
            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);
            // if (j < 100) std::cout << "remove: " << j << '\n';
        }

        Remove(pos[i]);
        // if (pos[i] < 100) std::cout << "big remove: " << pos[i] << '\n';
    }

    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:63:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for (int i = 0 ; i < s.size() ; i += MYLOG)
      |                          ~~^~~~~~~~~~
Anna.cpp: In function 'void Anna(int, std::vector<char>)':
Anna.cpp:143:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |     for (int i = 0 ; i < res.size() ; ++i)
      |                      ~~^~~~~~~~~~~~

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

Subtask #1
5.0 / 5.0

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

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 8436 KB Output is correct
2 Correct 40 ms 8328 KB Output is correct
3 Correct 40 ms 8300 KB Output is correct
4 Correct 40 ms 8364 KB Output is correct
5 Correct 40 ms 8452 KB Output is correct
6 Correct 40 ms 8316 KB Output is correct
7 Correct 40 ms 8468 KB Output is correct
8 Correct 40 ms 8392 KB Output is correct
9 Correct 40 ms 8464 KB Output is correct
10 Correct 40 ms 8284 KB Output is correct
11 Correct 40 ms 8364 KB Output is correct
12 Correct 40 ms 8316 KB Output is correct
13 Correct 46 ms 8328 KB Output is correct
14 Correct 44 ms 8420 KB Output is correct
15 Correct 42 ms 8588 KB Output is correct
16 Correct 41 ms 8284 KB Output is correct
17 Correct 44 ms 8520 KB Output is correct
18 Correct 44 ms 8304 KB Output is correct
19 Correct 44 ms 8316 KB Output is correct
20 Correct 40 ms 8416 KB Output is correct
21 Correct 42 ms 8556 KB Output is correct
22 Correct 43 ms 8312 KB Output is correct
23 Correct 39 ms 8420 KB Output is correct
24 Correct 45 ms 8384 KB Output is correct
25 Correct 45 ms 8332 KB Output is correct
26 Correct 44 ms 8320 KB Output is correct
27 Correct 44 ms 8368 KB Output is correct
28 Correct 43 ms 8172 KB Output is correct
29 Correct 44 ms 8300 KB Output is correct
30 Correct 45 ms 8348 KB Output is correct
31 Correct 45 ms 8308 KB Output is correct
32 Correct 40 ms 8416 KB Output is correct
33 Correct 40 ms 8296 KB Output is correct