oj.uz

Submission #713461

# Submission time Handle Problem Language Result Execution time Memory
713461 2023-03-22T04:47:13 Z marvinthang Ancient Machine (JOI21_ancient_machine) C++17
100 / 100
 61 ms 8184 KB 
/*************************************
*    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));
    }
}
/*************************************
*    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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 508 KB Output is correct
2 Correct 0 ms 516 KB Output is correct
3 Correct 0 ms 512 KB Output is correct
4 Correct 0 ms 516 KB Output is correct
5 Correct 1 ms 508 KB Output is correct
6 Correct 1 ms 508 KB Output is correct
7 Correct 1 ms 508 KB Output is correct
8 Correct 0 ms 508 KB Output is correct
9 Correct 1 ms 508 KB Output is correct
10 Correct 1 ms 516 KB Output is correct
11 Correct 1 ms 508 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 7792 KB Output is correct
2 Correct 53 ms 7688 KB Output is correct
3 Correct 47 ms 7640 KB Output is correct
4 Correct 46 ms 7628 KB Output is correct
5 Correct 49 ms 7688 KB Output is correct
6 Correct 47 ms 7732 KB Output is correct
7 Correct 46 ms 7676 KB Output is correct
8 Correct 55 ms 7688 KB Output is correct
9 Correct 49 ms 7768 KB Output is correct
10 Correct 50 ms 7668 KB Output is correct
11 Correct 47 ms 7688 KB Output is correct
12 Correct 49 ms 7784 KB Output is correct
13 Correct 55 ms 7668 KB Output is correct
14 Correct 55 ms 8152 KB Output is correct
15 Correct 52 ms 8184 KB Output is correct
16 Correct 52 ms 8064 KB Output is correct
17 Correct 55 ms 8168 KB Output is correct
18 Correct 56 ms 8164 KB Output is correct
19 Correct 60 ms 8156 KB Output is correct
20 Correct 49 ms 8064 KB Output is correct
21 Correct 50 ms 8176 KB Output is correct
22 Correct 55 ms 8080 KB Output is correct
23 Correct 50 ms 8152 KB Output is correct
24 Correct 46 ms 8168 KB Output is correct
25 Correct 56 ms 8144 KB Output is correct
26 Correct 53 ms 8156 KB Output is correct
27 Correct 57 ms 8080 KB Output is correct
28 Correct 57 ms 8164 KB Output is correct
29 Correct 55 ms 8128 KB Output is correct
30 Correct 61 ms 8068 KB Output is correct
31 Correct 57 ms 8064 KB Output is correct
32 Correct 49 ms 8156 KB Output is correct
33 Correct 60 ms 8156 KB Output is correct