Submission #853844

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
853844	2023-09-25T10:07:15 Z	danikoynov	Ancient Machine (JOI21_ancient_machine)	C++17	98 / 100	197 ms	87852 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 = 17;


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 = 17;

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	146 ms	79016 KB	Output is correct
2	Correct	146 ms	79032 KB	Output is correct
3	Correct	146 ms	79032 KB	Output is correct
4	Correct	145 ms	79016 KB	Output is correct
5	Correct	147 ms	79020 KB	Output is correct
6	Correct	145 ms	79020 KB	Output is correct
7	Correct	146 ms	79056 KB	Output is correct
8	Correct	144 ms	79272 KB	Output is correct
9	Correct	146 ms	79020 KB	Output is correct
10	Correct	148 ms	79052 KB	Output is correct
11	Correct	146 ms	79064 KB	Output is correct

Subtask #2

93.0 / 95.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	182 ms	86892 KB	Partially correct
2	Partially correct	182 ms	86892 KB	Partially correct
3	Partially correct	183 ms	86904 KB	Partially correct
4	Partially correct	181 ms	86776 KB	Partially correct
5	Partially correct	183 ms	86912 KB	Partially correct
6	Partially correct	182 ms	86892 KB	Partially correct
7	Partially correct	183 ms	86892 KB	Partially correct
8	Partially correct	184 ms	86872 KB	Partially correct
9	Partially correct	183 ms	86788 KB	Partially correct
10	Partially correct	186 ms	86896 KB	Partially correct
11	Partially correct	185 ms	86788 KB	Partially correct
12	Partially correct	188 ms	87152 KB	Partially correct
13	Partially correct	187 ms	86612 KB	Partially correct
14	Partially correct	188 ms	87004 KB	Partially correct
15	Partially correct	186 ms	86884 KB	Partially correct
16	Partially correct	188 ms	86900 KB	Partially correct
17	Partially correct	189 ms	86652 KB	Partially correct
18	Partially correct	191 ms	87656 KB	Partially correct
19	Partially correct	190 ms	87588 KB	Partially correct
20	Partially correct	182 ms	86772 KB	Partially correct
21	Partially correct	188 ms	86892 KB	Partially correct
22	Partially correct	188 ms	86764 KB	Partially correct
23	Partially correct	183 ms	86796 KB	Partially correct
24	Partially correct	184 ms	86868 KB	Partially correct
25	Partially correct	197 ms	87568 KB	Partially correct
26	Partially correct	188 ms	86764 KB	Partially correct
27	Partially correct	194 ms	87852 KB	Partially correct
28	Partially correct	192 ms	86784 KB	Partially correct
29	Partially correct	189 ms	87588 KB	Partially correct
30	Partially correct	191 ms	87444 KB	Partially correct
31	Partially correct	190 ms	87592 KB	Partially correct
32	Partially correct	182 ms	86844 KB	Partially correct
33	Partially correct	184 ms	86892 KB	Partially correct