제출 #931367

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
931367		boris_mihov	Ancient Machine (JOI21_ancient_machine)	C++17	100 / 100	50 ms	8584 KiB

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::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);
}

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

컴파일 시 표준 에러 (stderr) 메시지

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 / 5
• Subtask 2: 95 / 95