oj.uz

Submission #931367

# Submission time Handle Problem Language Result Execution time Memory
931367 2024-02-21T16:36:30 Z boris_mihov Ancient Machine (JOI21_ancient_machine) C++17
100 / 100
 50 ms 8584 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::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 (s[j] == '1') currNum += fib[j - i];
            }
            
            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)
    {
        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';
                }
            }

            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];
    }

    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';
        } else if (foundX && s[i] == 'Z' && ((res.back() == '0' && (i + 1 == N || s[i + 1] != 'Z'))))
        {
            res += '1';
        } else if (s[i] == 'Z' && i == xPos + 1)
        {
            res += '0';
            hasZinFront = true;
        } else
        {
            res += '0';
        }
    }

    FibbonacciConverter converter;
    res = converter.getString(res);

    for (int i = 0 ; i < res.size() ; ++i)
    {
        Send(res[i] - '0');
    }

    Send(hasZinFront);
}

#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;
            std::string sequence;
            for (int j = i ; j < i + BUCKET_SIZE ; ++j)
            {
                sequence += s[j];
                if (s[j] == '1') currNum += fibB[j - i];
            }
            
            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)
    {
        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';
                }
            }

            std::reverse(toAdd.begin(), toAdd.end());
            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);

    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) 
                {
                    s[i + 1] = '1';
                }
            }

            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:22:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for (int i = 0 ; i < s.size() ; i += BUCKET_SIZE)
      |                          ~~^~~~~~~~~~
Anna.cpp: In member function 'std::string FibbonacciConverter::fromString(std::string)':
Anna.cpp:50:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for (int i = 0 ; i < s.size() ; i += MYLOG)
      |                          ~~^~~~~~~~~~
Anna.cpp: In function 'void Anna(int, std::vector<char>)':
Anna.cpp:119:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     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:143:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |     for (int i = 1 ; i < pos.size() ; ++i)
      |                      ~~^~~~~~~~~~~~
Bruno.cpp:108:9: warning: unused variable 'added' [-Wunused-variable]
  108 |     int added = 0;
      |         ^~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 8072 KB Output is correct
2 Correct 41 ms 7960 KB Output is correct
3 Correct 42 ms 8144 KB Output is correct
4 Correct 39 ms 8020 KB Output is correct
5 Correct 40 ms 8088 KB Output is correct
6 Correct 40 ms 7984 KB Output is correct
7 Correct 40 ms 8136 KB Output is correct
8 Correct 39 ms 8088 KB Output is correct
9 Correct 40 ms 8060 KB Output is correct
10 Correct 40 ms 8084 KB Output is correct
11 Correct 46 ms 8104 KB Output is correct
12 Correct 41 ms 8068 KB Output is correct
13 Correct 45 ms 8096 KB Output is correct
14 Correct 47 ms 8136 KB Output is correct
15 Correct 42 ms 7920 KB Output is correct
16 Correct 47 ms 7936 KB Output is correct
17 Correct 44 ms 7968 KB Output is correct
18 Correct 45 ms 8156 KB Output is correct
19 Correct 48 ms 8052 KB Output is correct
20 Correct 39 ms 8044 KB Output is correct
21 Correct 39 ms 8048 KB Output is correct
22 Correct 44 ms 8064 KB Output is correct
23 Correct 39 ms 8020 KB Output is correct
24 Correct 39 ms 8024 KB Output is correct
25 Correct 44 ms 8060 KB Output is correct
26 Correct 46 ms 7932 KB Output is correct
27 Correct 44 ms 8068 KB Output is correct
28 Correct 50 ms 8584 KB Output is correct
29 Correct 44 ms 8120 KB Output is correct
30 Correct 45 ms 8044 KB Output is correct
31 Correct 45 ms 7956 KB Output is correct
32 Correct 39 ms 7988 KB Output is correct
33 Correct 39 ms 8092 KB Output is correct