Submission #853850

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
853850	2023-09-25T10:10:15 Z	danikoynov	Ancient Machine (JOI21_ancient_machine)	C++17	94 / 100	663 ms	206844 KB

Anna

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



const int maxbit = 26;

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


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

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

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	593 ms	198224 KB	Output is correct
2	Correct	578 ms	197980 KB	Output is correct
3	Correct	663 ms	198060 KB	Output is correct
4	Correct	565 ms	197992 KB	Output is correct
5	Correct	581 ms	198044 KB	Output is correct
6	Correct	570 ms	198148 KB	Output is correct
7	Correct	653 ms	197808 KB	Output is correct
8	Correct	579 ms	197780 KB	Output is correct
9	Correct	568 ms	197876 KB	Output is correct
10	Correct	574 ms	197972 KB	Output is correct
11	Correct	576 ms	198124 KB	Output is correct

Subtask #2

89.0 / 95.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	603 ms	205864 KB	Partially correct
2	Partially correct	619 ms	205888 KB	Partially correct
3	Partially correct	613 ms	206284 KB	Partially correct
4	Partially correct	612 ms	205920 KB	Partially correct
5	Partially correct	607 ms	205924 KB	Partially correct
6	Partially correct	607 ms	206040 KB	Partially correct
7	Partially correct	618 ms	205796 KB	Partially correct
8	Partially correct	613 ms	206140 KB	Partially correct
9	Partially correct	610 ms	206204 KB	Partially correct
10	Partially correct	605 ms	205908 KB	Partially correct
11	Partially correct	607 ms	205760 KB	Partially correct
12	Partially correct	611 ms	205952 KB	Partially correct
13	Partially correct	620 ms	206064 KB	Partially correct
14	Partially correct	615 ms	206192 KB	Partially correct
15	Partially correct	619 ms	206248 KB	Partially correct
16	Partially correct	611 ms	206144 KB	Partially correct
17	Partially correct	608 ms	205704 KB	Partially correct
18	Partially correct	623 ms	206648 KB	Partially correct
19	Partially correct	623 ms	206668 KB	Partially correct
20	Partially correct	606 ms	206044 KB	Partially correct
21	Partially correct	606 ms	206116 KB	Partially correct
22	Partially correct	618 ms	206184 KB	Partially correct
23	Partially correct	611 ms	205920 KB	Partially correct
24	Partially correct	608 ms	205936 KB	Partially correct
25	Partially correct	613 ms	206520 KB	Partially correct
26	Partially correct	617 ms	206024 KB	Partially correct
27	Partially correct	615 ms	206632 KB	Partially correct
28	Partially correct	614 ms	205752 KB	Partially correct
29	Partially correct	624 ms	206844 KB	Partially correct
30	Partially correct	616 ms	206628 KB	Partially correct
31	Partially correct	615 ms	206508 KB	Partially correct
32	Partially correct	619 ms	205856 KB	Partially correct
33	Partially correct	612 ms	206132 KB	Partially correct