Submission #713461

#	Time	Username	Problem	Language	Result	Execution time	Memory
713461		marvinthang	Ancient Machine (JOI21_ancient_machine)	C++17	100 / 100	61 ms	8184 KiB

Anna

/*************************************
*    author: marvinthang             *
*    created: 21.03.2023 23:00:23    *
*************************************/

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

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 

namespace {

}

void Anna(int n, vector <char> s) {
    vector <long long> f(64);
    f[0] = 1; f[1] = 2;
    FOR(i, 2, 64) f[i] = f[i - 1] + f[i - 2];
    auto find_pos = [&] (string s) {
        long long res = 0;
        REP(i, 63) if (s[i] == '1') res += f[62 - i];
        return res;
    };
    bool first_x = false;
    string res;
    REP(i, n) {
        if (!first_x && s[i] == 'X') {
            first_x = true;
            res += '1';
            ++i;
            if (i < n) {
                res += '0';
                if (s[i] == 'Z') Send(1);
                else Send(0);
            } else Send(0);
        } else if (first_x && s[i] == 'Z') {
            if (res.back() == '1') res.back() = '0';
            res += '1';
        }
        else res += '0';
    }
    while (res.size() % 63) res += '0';
    for (int i = 0; i < res.size(); i += 63) {
        string s = res.substr(i, 63);
        long long x = find_pos(s);
        REP(i, 44) Send(BIT(x, i));
    }
}

Bruno

/*************************************
*    author: marvinthang             *
*    created: 21.03.2023 23:03:23    *
*************************************/

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

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 

namespace {

}

void Bruno(int N, int L, std::vector<int> A) {
    vector <long long> f(64);
    f[0] = 1; f[1] = 2;
    FOR(i, 2, 64) f[i] = f[i - 1] + f[i - 2];
    auto find_string = [&] (long long k) {
        string res;
        REP(i, 63) {
            if (k <= f[62 - i]) res += '0';
            else {
                res += '1';
                k -= f[62 - i];
            }
        }
        return res;
    };
    string s;
    for (int i = 1; i < A.size(); i += 44) {
        long long res = 0;
        FORD(j, i + 44, i) res = res * 2 + A[j];
        ++res;
        s += find_string(res);
    }

    int first_x = -1;
    int last = -1;
    REP(i, N) if (s[i] == '1') {
        if (first_x == -1) {
            first_x = i;
            REP(j, i) Remove(j);
            if (A[0]) {
                Remove(i + 1);
                ++i;
            }
        } else {
            FORD(j, i, last + 1) Remove(j);
            Remove(i);
        }
        last = i;
    }
    FOR(j, last + 1, N) Remove(j);
    if (first_x != -1) Remove(first_x);
}

Compilation message (stderr)

Anna.cpp: In function 'void Anna(int, std::vector<char>)':
Anna.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i = 0; i < res.size(); i += 63) {
      |                     ~~^~~~~~~~~~~~

Bruno.cpp: In function 'void Bruno(int, int, std::vector<int>)':
Bruno.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i = 1; i < A.size(); i += 44) {
      |                     ~~^~~~~~~~~~

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