Submission #853843

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
853843	2023-09-25T10:06:29 Z	danikoynov	Ancient Machine (JOI21_ancient_machine)	C++17	90 / 100	194 ms	88140 KB

Anna

#include "Anna.h"
#include <vector>
#include <bits/stdc++.h>



const int maxbit = 24;

int to[(1 << maxbit)], rev[(1 << maxbit)];
void create_matching()
{
    int cnt = 0;
    for (int mask = 0; mask < (1 << maxbit); mask ++)
    {
        bool tf = true;
        for (int bit = 1; bit < maxbit; bit ++)
        {
            if ((mask & (1 << bit)) > 0 && (mask & (1 << (bit - 1))) > 0)
            {
                tf = false;
                break;
            }
        }

        if (!tf)
            continue;
        to[mask] = cnt;
        rev[cnt] = mask;
        cnt ++;
    }
}

const int tobit = 18;


std::vector < int > go_to_fibonacci(std::vector < int > seq)
{

    std::vector < int > res;
    int last = 0;
    for (int i = 0; i < seq.size(); i ++)
    {
        last = last + seq[i] * (1 << (i % maxbit));
        if ((i % maxbit) == maxbit - 1)
        {
            int x = to[last];
            for (int bit = 0; bit < tobit; bit ++)
            {
                if ((x & (1 << bit)) > 0)
                    res.push_back(1);
                else
                    res.push_back(0);
            }
            last = 0;
        }
    }
    if (seq.size() % maxbit != 0)
    {

                int x = to[last];
            for (int bit = 0; bit < tobit; bit ++)
            {
                if ((x & (1 << bit)) > 0)
                    res.push_back(1);
                else
                    res.push_back(0);
            }

            }
            return res;

}




void Anna(int N, std::vector<char> S)
{
    create_matching();
    std::vector < int > seq;
    for (int i = 0; i < N; i ++)
    {
        if (S[i] == 'Z' && (i == N - 1 || S[i + 1] != 'Z'))
            seq.push_back(1);
        else
            seq.push_back(0);
    }

    seq = go_to_fibonacci(seq);
    ///std::cout << seq.size() << std::endl;
    for (int i = 0; i < seq.size(); i ++)
        Send(seq[i]);
        ///std:: cout << "size " << seq.size() << std::endl;
    int pt = 0;
    while(pt < N && S[pt] != 'X')
        pt ++;
    for (int bit = 0; bit < 20; bit ++)
    {
        if ((pt & (1 << bit)) > 0)
            Send(1);
        else
            Send(0);
    }

}

Bruno

#include "Bruno.h"
#include <vector>
#include <iostream>
#include <bits/stdc++.h>
namespace
{
const int maxn = 1e5 + 10;
int variable_example = 0;

int FunctionExample(int P)
{
    return 1 - P;
}
char c[maxn];
}  // namespace

void sub_solve()
{

}

const int MAXBIT = 24;

int TO[(1 << MAXBIT)], REV[(1 << MAXBIT)];
void build_matching()
{
    int cnt = 0;
    for (int mask = 0; mask < (1 << MAXBIT); mask ++)
    {
        bool tf = true;
        for (int bit = 1; bit < MAXBIT; bit ++)
        {
            if ((mask & (1 << bit)) > 0 && (mask & (1 << (bit - 1))) > 0)
            {
                tf = false;
                break;
            }
        }

        if (!tf)
            continue;
        TO[mask] = cnt;
        REV[cnt] = mask;
        cnt ++;
    }
}

const int TOBIT = 18;

std::vector < int > go_to_binary(std::vector < int > seq)
{
    build_matching();
        std::vector < int > res;
    int last = 0;
    for (int i = 0; i < seq.size(); i ++)
    {
        last = last + seq[i] * (1 << (i % TOBIT));
        if ((i % TOBIT) == TOBIT - 1)
        {
            int x = REV[last];
            for (int bit = 0; bit < MAXBIT; bit ++)
            {
                if ((x & (1 << bit)) > 0)
                    res.push_back(1);
                else
                    res.push_back(0);
            }
            last = 0;
        }
    }
                int x = REV[last];
            for (int bit = 0; bit < MAXBIT; bit ++)
            {
                if ((x & (1 << bit)) > 0)
                    res.push_back(1);
                else
                    res.push_back(0);
            }
            return res;
}
void Bruno(int N, int L, std::vector<int> A)
{
    int main_lenght = N / MAXBIT;
    if (N % MAXBIT != 0)
        main_lenght ++;
    main_lenght *= TOBIT;
    ///std::cout << main_lenght << std::endl;
    int pt = 0;
    assert(A.size() == main_lenght + 20);
    for (int bit = 0; bit < 20; bit ++)
    {
        pt = pt + A[bit + main_lenght] * (1 << bit);
    }

    ///assert(pt >= 0 && pt <= N);

    for (int i = 0; i < pt; i ++)
        Remove(i);

        for (int i = 0; i < 20; i ++)
            A.pop_back();
        A = go_to_binary(A);

    assert(A.size() >= N);
    std::vector < int > zpos;
    for (int i = pt; i < N; i ++)
    {

        if (A[i] == 1)
            zpos.push_back(i);
    }


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

    for (int i = N - 1; i > last; i --)
        Remove(i);
    if (pt != N)
        Remove(pt);

    /**for (int i = 0; i < N; i ++)
        std::cout << c[i] << " ";
    std::cout << std::endl;*/
}

Compilation message

Anna.cpp: In function 'std::vector<int> go_to_fibonacci(std::vector<int>)':
Anna.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = 0; i < seq.size(); i ++)
      |                     ~~^~~~~~~~~~~~
Anna.cpp: In function 'void Anna(int, std::vector<char>)':
Anna.cpp:91:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for (int i = 0; i < seq.size(); i ++)
      |                     ~~^~~~~~~~~~~~

Bruno.cpp: In function 'std::vector<int> go_to_binary(std::vector<int>)':
Bruno.cpp:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i = 0; i < seq.size(); i ++)
      |                     ~~^~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from Bruno.cpp:4:
Bruno.cpp: In function 'void Bruno(int, int, std::vector<int>)':
Bruno.cpp:89:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |     assert(A.size() == main_lenght + 20);
      |            ~~~~~~~~~^~~~~~~~~~~~~~~~~~~
Bruno.cpp:97:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   97 |     for (int i = 0; i < pt; i ++)
      |     ^~~
Bruno.cpp:100:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  100 |         for (int i = 0; i < 20; i ++)
      |         ^~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from Bruno.cpp:4:
Bruno.cpp:104:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  104 |     assert(A.size() >= N);
      |            ~~~~~~~~~^~~~
Bruno.cpp:115:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for (int i = 0; i < zpos.size(); i ++)
      |                     ~~^~~~~~~~~~~~~
Bruno.cpp: At global scope:
Bruno.cpp:14:6: warning: '{anonymous}::c' defined but not used [-Wunused-variable]
   14 | char c[maxn];
      |      ^
Bruno.cpp:10:5: warning: 'int {anonymous}::FunctionExample(int)' defined but not used [-Wunused-function]
   10 | int FunctionExample(int P)
      |     ^~~~~~~~~~~~~~~
Bruno.cpp:8:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
    8 | int variable_example = 0;
      |     ^~~~~~~~~~~~~~~~

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	148 ms	79016 KB	Output is correct
2	Correct	146 ms	79028 KB	Output is correct
3	Correct	147 ms	79016 KB	Output is correct
4	Correct	146 ms	79080 KB	Output is correct
5	Correct	153 ms	79640 KB	Output is correct
6	Correct	146 ms	79016 KB	Output is correct
7	Correct	148 ms	79084 KB	Output is correct
8	Correct	143 ms	79016 KB	Output is correct
9	Correct	149 ms	79288 KB	Output is correct
10	Correct	144 ms	79016 KB	Output is correct
11	Correct	145 ms	78908 KB	Output is correct

Subtask #2

85.0 / 95.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	186 ms	86952 KB	Partially correct
2	Partially correct	185 ms	86884 KB	Partially correct
3	Partially correct	191 ms	87108 KB	Partially correct
4	Partially correct	182 ms	86868 KB	Partially correct
5	Partially correct	189 ms	87272 KB	Partially correct
6	Partially correct	184 ms	86868 KB	Partially correct
7	Partially correct	183 ms	86868 KB	Partially correct
8	Partially correct	185 ms	86864 KB	Partially correct
9	Partially correct	187 ms	87156 KB	Partially correct
10	Partially correct	183 ms	86784 KB	Partially correct
11	Partially correct	183 ms	86880 KB	Partially correct
12	Partially correct	182 ms	86804 KB	Partially correct
13	Partially correct	188 ms	86784 KB	Partially correct
14	Partially correct	190 ms	87044 KB	Partially correct
15	Partially correct	189 ms	86836 KB	Partially correct
16	Partially correct	185 ms	86868 KB	Partially correct
17	Partially correct	190 ms	86708 KB	Partially correct
18	Partially correct	190 ms	87684 KB	Partially correct
19	Partially correct	189 ms	87520 KB	Partially correct
20	Partially correct	189 ms	86848 KB	Partially correct
21	Partially correct	184 ms	86760 KB	Partially correct
22	Partially correct	189 ms	86848 KB	Partially correct
23	Partially correct	186 ms	86852 KB	Partially correct
24	Partially correct	192 ms	86792 KB	Partially correct
25	Partially correct	190 ms	87636 KB	Partially correct
26	Partially correct	189 ms	87120 KB	Partially correct
27	Partially correct	189 ms	87604 KB	Partially correct
28	Partially correct	188 ms	86836 KB	Partially correct
29	Partially correct	189 ms	87616 KB	Partially correct
30	Partially correct	188 ms	87636 KB	Partially correct
31	Partially correct	194 ms	88140 KB	Partially correct
32	Partially correct	184 ms	86880 KB	Partially correct
33	Partially correct	188 ms	86888 KB	Partially correct