Submission #951304

#	Time	Username	Problem	Language	Result	Execution time	Memory
951304		andrei_boaca	Ancient Machine (JOI21_ancient_machine)	C++17	100 / 100	54 ms	9592 KiB

Anna

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

using namespace std;
typedef long long ll;
namespace
{
    ll dp[105][2];
    int dir;
    vector<int> getsir(vector<char> s)
    {
        int n=s.size();
        int N=n;
        int zy=0,yx=0;
        for(int i=0;i+1<n;i++)
        {
            if(s[i]=='Z'&&s[i+1]=='Y')
                zy++;
            if(s[i]=='Y'&&s[i+1]=='X')
                yx++;
        }
        char cz='Z',cx='X';
        vector<int> rez;
        int lastz=-1;
        bool havex=0;
        for(int i=N-1;i>=0;i--)
            if(s[i]==cz)
            {
                lastz=i;
                break;
            }
        if(lastz==-1)
        {
            rez.push_back(0);
            return rez;
        }
        for(int i=0;i<N;i++)
        {
            if(s[i]==cx)
            {
                if(!havex)
                {
                    rez.push_back(1);
                    rez.push_back(0);
                }
                else
                    rez.push_back(0);
                havex=1;
                continue;
            }
            if(!havex)
            {
                rez.push_back(0);
                continue;
            }
            if(s[i]==cz&&(i==N||s[i+1]=='Y'||i==lastz))
                rez.push_back(1);
            else
                rez.push_back(0);
        }
        return rez;
    }
    vector<int> codif(vector<int> vec)
    {
        ll cnt=0;
        for(int i=0;i<vec.size();i++)
            if(vec[i]==1)
            {
                ll lft=(int)vec.size()-i-1;
                cnt+=dp[lft][0]+dp[lft][1];
            }
        //cout<<cnt<<'\n';
        vector<int> rez;
        for(int bit=43;bit>=0;bit--)
        {
            if((cnt>>bit)&1)
                rez.push_back(1);
            else
                rez.push_back(0);
        }
        return rez;
    }
}
void Anna(int N, std::vector<char> S)
{
    dp[0][0]=1;
    dp[0][1]=0;
    dp[1][0]=dp[1][1]=1;
    for(ll i=2;i<=70;i++)
    {
        dp[i][0]=dp[i-1][0]+dp[i-1][1];
        dp[i][1]=dp[i-1][0];
    }
    dir=0;
    vector<int> sol,sir;
    sir=getsir(S);
    if(sir.size()==1)
    {
        Send(sir[0]);
        return;
    }
    int nr1=0;
    /*for(int i=1;i<sir.size();i++)
        assert(sir[i]+sir[i-1]<2);*/
    for(int i=0;i<sir.size();i+=63)
    {
        vector<int> vec;
        for(int j=i;j<sir.size()&&j<i+63;j++)
            vec.push_back(sir[j]);
        while(vec.size()<63)
            vec.push_back(0);
        vector<int> t=codif(vec);
        for(int j:t)
            sol.push_back(j);
    }
    for(int i:sol)
        Send(i);
}

Bruno

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

using namespace std;
typedef long long ll;
namespace
{
    ll depeu[105][2];
    vector<int> decod(ll num)
    {
        vector<int> rez;
        for(int i=0;i<63;i++)
        {
            ll lg=63-i-1;
            if(depeu[lg][0]+depeu[lg][1]<=num)
            {
                num-=(depeu[lg][0]+depeu[lg][1]);
                rez.push_back(1);
            }
            else
                rez.push_back(0);
        }
        return rez;
    }
}

void Bruno(int N, int L, std::vector<int> A)
{
    depeu[0][0]=1;
    depeu[0][1]=0;
    depeu[1][0]=1;
    depeu[1][1]=1;
    for(ll i=2;i<=70;i++)
    {
        depeu[i][0]=depeu[i-1][0]+depeu[i-1][1];
        depeu[i][1]=depeu[i-1][0];
    }
    vector<int> sir;
    if(L==1)
    {
        for(int i=0;i<N;i++)
            Remove(i);
        return;
    }
    for(int i=0;i<A.size();i+=44)
    {
        ll num=0;
        for(int j=i;j<A.size()&&j<i+44;j++)
            num=num*2LL+A[j];
        //cout<<num<<'\n';
        vector<int> vals=decod(num);
        for(int j=0;j<vals.size()&&sir.size()<N+1;j++)
            sir.push_back(vals[j]);
    }
    vector<int> aux;
    int elim=-1;
    for(int i=0;i<sir.size();i++)
        if(sir[i]==1)
        {
            elim=i+1;
            break;
        }
    for(int i=0;i<sir.size();i++)
        if(i!=elim)
            aux.push_back(sir[i]);
    /*for(int i:aux)
        cout<<i<<' ';
    cout<<'\n';*/
    A=aux;
    int lft=-1;
    for(int i=0;i<A.size();i++)
        if(A[i]==1)
        {
            lft=i;
            break;
        }
    //assert(A.size()==N);
    if(lft==-1)
    {
        for(int i=0;i<N;i++)
            Remove(i);
        return;
    }
    for(int i=0;i<lft;i++)
        Remove(i);
    for(int i=lft+1;i<A.size();i++)
        if(A[i]==1)
        {
            for(int j=i-1;A[j]==0;j--)
                Remove(j);
            Remove(i);
        }
    for(int i=N-1;A[i]==0;i--)
        Remove(i);
    Remove(lft);
}

Compilation message (stderr)

Anna.cpp: In function 'std::vector<int> {anonymous}::codif(std::vector<int>)':
Anna.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for(int i=0;i<vec.size();i++)
      |                     ~^~~~~~~~~~~
Anna.cpp: In function 'void Anna(int, std::vector<char>)':
Anna.cpp:106:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for(int i=0;i<sir.size();i+=63)
      |                 ~^~~~~~~~~~~
Anna.cpp:109:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         for(int j=i;j<sir.size()&&j<i+63;j++)
      |                     ~^~~~~~~~~~~
Anna.cpp:103:9: warning: unused variable 'nr1' [-Wunused-variable]
  103 |     int nr1=0;
      |         ^~~

Bruno.cpp: In function 'void Bruno(int, int, std::vector<int>)':
Bruno.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i=0;i<A.size();i+=44)
      |                 ~^~~~~~~~~
Bruno.cpp:49:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for(int j=i;j<A.size()&&j<i+44;j++)
      |                     ~^~~~~~~~~
Bruno.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int j=0;j<vals.size()&&sir.size()<N+1;j++)
      |                     ~^~~~~~~~~~~~
Bruno.cpp:53:46: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |         for(int j=0;j<vals.size()&&sir.size()<N+1;j++)
      |                                    ~~~~~~~~~~^~~~
Bruno.cpp:58:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i=0;i<sir.size();i++)
      |                 ~^~~~~~~~~~~
Bruno.cpp:64:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int i=0;i<sir.size();i++)
      |                 ~^~~~~~~~~~~
Bruno.cpp:72:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int i=0;i<A.size();i++)
      |                 ~^~~~~~~~~
Bruno.cpp:87:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int i=lft+1;i<A.size();i++)
      |                     ~^~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95