oj.uz

Submission #853846

# Submission time Handle Problem Language Result Execution time Memory
853846 2023-09-25T10:08:02 Z danikoynov Ancient Machine (JOI21_ancient_machine) C++17
5 / 100
 360 ms 132008 KB 
#include "Anna.h"
#include <vector>
#include <bits/stdc++.h>



const int maxbit = 25;

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

}

#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 = 25;

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 293 ms 124304 KB Output is correct
2 Correct 293 ms 124248 KB Output is correct
3 Correct 302 ms 124480 KB Output is correct
4 Correct 289 ms 124072 KB Output is correct
5 Correct 291 ms 124256 KB Output is correct
6 Correct 360 ms 124392 KB Output is correct
7 Correct 289 ms 124040 KB Output is correct
8 Correct 296 ms 124400 KB Output is correct
9 Correct 303 ms 124228 KB Output is correct
10 Correct 302 ms 124280 KB Output is correct
11 Correct 287 ms 124140 KB Output is correct

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Incorrect 330 ms 132008 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -