Submission #537876

#	Time	Username	Problem	Language	Result	Execution time	Memory
537876		Jarif_Rahman	Ancient Machine (JOI21_ancient_machine)	C++17	100 / 100	60 ms	8504 KiB

Anna

#include "Anna.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

namespace {
    vector<ll> fib(70, 0);

    void send_number(ll x){
        for(int i = 0; i < 44; i++){
            Send(x%2);
            x/=2;
        }
    }

    void send_encoded(vector<int> v){
        int n = v.size();
        while(n%63 != 0) n++, v.pb(0);
        for(int i = 0; i < n; i+=63){
            vector<ll> dp(63, 0);
            if(v[i] == 0 && v[i+1] == 0) dp[0] = 0, dp[1] = 0;
            else if(v[i] == 0 && v[i+1] == 1) dp[0] = 0, dp[1] = fib[3]+dp[0];
            else if(v[i] == 1 && v[i+1] == 0) dp[0] = 1, dp[1] = 1;
            for(int j = i+2; j < i+63; j++){
                if(v[j] == 0) dp[j-i] = dp[j-i-1];
                else dp[j-i] = fib[j-i+2]+dp[j-i-2];
            }
            send_number(dp[62]);
        }
    }
}

void Anna(int n, vector<char> s){

    fib[1] = 1;
    for(int i = 2; i < 70; i++) fib[i] = fib[i-1]+fib[i-2];

    vector<int> rt(n, 0);
    int fx = -1;
    for(int i = 0; i < n; i++) if(s[i] == 'X'){
        fx = i;
        break;
    }

    if(fx == -1){
        send_encoded(rt);
        send_number(0);
        return;
    }

    for(int i = fx+1; i < n; i++) if(s[i] == 'Z' && (i == n-1 || s[i+1] != 'Z')) rt[i] = 1;

    send_encoded(rt);
    send_number(fx);
}

Bruno

#include "Bruno.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

namespace {
    vector<ll> fib(70, 0);

    ll get_number(vector<int> x){
        ll rt = 0;
        for(int i = 44; i >= 0; i--){
            if(x[i] == 1) rt+=(1LL<<i);
        }
        return rt;
    }

    vector<int> decode(vector<int> v){
        vector<int> rt;
        int n = v.size();
        for(int i = 0; i < n; i+=44){
            vector<int> sth;
            for(int j = i; j < i+44; j++) sth.pb(v[j]);
            ll c = get_number(sth);
            vector<int> cur;
            for(int j = 62; j >= 0; j--){
                if(c >= fib[j+2]){
                    cur.pb(1);
                    cur.pb(0);
                    c-=fib[j+2];
                    j--;
                }
                else{
                    cur.pb(0);
                }
            }
            if(cur.size() > 63) cur.pop_back();
            reverse(cur.begin(), cur.end());
            rt.insert(rt.end(), cur.begin(), cur.end());
        }
        return rt;
    }
}

void Bruno(int n, int m, vector<int> A){
    fib[1] = 1;
    for(int i = 2; i < 70; i++) fib[i] = fib[i-1]+fib[i-2];

    vector<int> sth;
    for(int i = 0; i < 44; i++){
        sth.pb(A.back());
        A.pop_back();
    }
    reverse(sth.begin(), sth.end());
    int fx = get_number(sth);

    A = decode(A);
    while(A.size() != n) A.pop_back();

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

    int ls = fx+1;
    
    for(int i = fx+1; i < n; i++){
        if(A[i] != 1) continue;
        for(int j = i-1; j >= ls; j--) Remove(j);
        Remove(i);
        ls = i+1;
    }

    Remove(fx);

    for(int i = ls; i < n; i++) Remove(i);
}

Compilation message (stderr)

Bruno.cpp: In function 'void Bruno(int, int, std::vector<int>)':
Bruno.cpp:61:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |     while(A.size() != n) A.pop_back();
      |           ~~~~~~~~~^~~~

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