Submission #1150737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150737		yeyso	Ancient Machine (JOI21_ancient_machine)	C++20	100 / 100	43 ms	6832 KiB

Anna

#include "Anna.h"
using namespace std;
#include <bits/stdc++.h>
#define lint __uint128_t
#define block_size 63
#define compressed 44
namespace {
    string plint(lint num) {
        string result;
        while (num > 0) {
            result = char('0' + (num % 10)) + result;
            num /= 10;
        }
        return result.empty() ? "0" : result;
    }
    void to_binary(lint n, vector<int> &res){
        if (n > 1) {
            to_binary(n / 2, res);  
        }
        res.push_back(n % 2);
    }
}
void Anna(int N, vector<char> S) {
    vector<lint> z(block_size, 0);
    z[0] = 1;
    z[1] = 2;
    for(int i = 2; i < block_size; i ++){
        z[i] = z[i-1] + z[i-2];
    }
    int pos = N;
    vector<int> A;
    for(int i = 0; i < S.size(); i ++){
        if(S[i] != 'X'){
            A.push_back(0);
        } else {
            A.push_back(1);
            A.push_back(0);
            pos = i;
            break;
        }
    }
    int cur = pos;
    for(int i = pos + 1; i < N; i ++){
        if(S[i] == 'Z'){
            if(i < N - 1){
                if(S[i+1] != 'Z'){
                    A.push_back(1);
                } else {
                    A.push_back(0);
                }
            } else {
                A.push_back(1);
            }
        } else {
            A.push_back(0);
        }
    }
    vector<int> message;
    for(int i = 0; i < A.size(); i += block_size){
        lint res = 0;
        for(int j = i; j < min((int)(i + block_size), (int)A.size()); j ++){
            if(A[j] == 1){
                res += z[j % block_size];
            }
        }
        vector<int> packet;
        to_binary(res, packet);
        for(int j = packet.size() - 1; j >= 0; j --){
            message.push_back(packet[j]);
        }
        for(int j = packet.size(); j < compressed; j ++){
            message.push_back(0);
        }
    }
    for(int i = 0; i < message.size(); i ++){
        Send(message[i]);
    }
}
/*
g++ -std=gnu++17 -O2 -fsigned-char -o grader grader.cpp ancientmachine.cpp Bruno.cpp
8
X Y X Z Y X Y Z
1 0 0 1 0 0 0 1

6
Y Z Y Z Y Z

block_size
X Y Z X Y Z X Y Z X Y Z X Y Z X Y Z X Y Z X Y Z X Y Z X Y Z X Y Z X Y Z X Y Z X Y Z X Y Z X X X X X
X Y Z X Y Z X Y Z X Y Z X Y Z X Y Z X Y Z X Y Z X Y Z X Y Z X Y Z X Y Z X Y Z X Y Z X Y Z X X X X X


Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y 
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y 
Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y 


X X X X X X Y X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X
X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X
X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X
X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X

X Y Z Z Y X X Z Y X Y Z X X Y Z X Y Z X Y Z Z Y X X Z Y X Y Z X Y Z X X Y Z X Y Z Z X Y X X Y Z Y Z X Y Z Z Y X X Z Y X Y Z X X Y Z X Y Z X Y Z Z Y X X 
Z Y X Y Z X Y Z X X Y Z X Y Z Z X Y X X Y Z Y Z Y Z Y Z Y Z 
X X Y Y Z Z Y X Y X Z Y X X Y Y Z Z Y X Y X Z Y X X Y Y Z Z Y X Y X Z Y X X Y Y Z Z Y X Y X Z Y Z Z
*/

Bruno

#include "Bruno.h"
using namespace std; 
#define lint __uint128_t
#include <bits/stdc++.h>
#define block_size 63
#define compressed 44
namespace {
    string plint(lint num) {
        string result;
        while (num > 0) {
            result = char('0' + (num % 10)) + result;
            num /= 10;
        }
        return result.empty() ? "0" : result;
    }
}
void Bruno(int N, int L, vector<int> A) {
    vector<int> A2;
    vector<lint> z(block_size, 0);
    z[0] = 1;
    z[1] = 2;
    for(int i = 2; i < block_size; i ++){
        z[i] = z[i-1] + z[i-2];
    }
    for(int i = 0; i < A.size(); i += compressed){
        lint cur = 0;
        for(int j = i; j < min((int)A.size(), (int)(i + compressed)); j ++){
            cur += (lint)A[j] * ((lint)1 << (j % compressed));
        }
        vector<int> output;
        for(int j = z.size() - 1; j >= 0; j --){
            if(cur >= z[j]){
                output.push_back(1);
                cur -= z[j];
            } else {
                output.push_back(0);
            }
        }
        for(int j = output.size() - 1; j >= 0; j --){
            A2.push_back(output[j]);
        } 
    }
    vector<int> A3;
    int i = 0;
    int seen = 0;
    while(i < A2.size()){
        A3.push_back(A2[i]);
        if(A2[i] == 1 && !seen){
            i ++;
            seen = 1;
        }
        i ++;
    }
    A2 = A3;
    int pos = -1;
    for(int i = 0; i < N; i ++){
        if(A2[i] == 0){
            Remove(i); 
        } else {
            pos = i;
            break;
        }
    }
    if(pos == -1) return;
    int cur = pos;
    for(int i = pos + 1; i < N; i++){
        if(A2[i] == 1){
            for(int j = i - 1; j > cur; j --){
                Remove(j); 
            }
            Remove(i); 
            cur = i;
        }
    }
    for(int i = N - 1; i > cur; i--){ 
        Remove(i); 
    }
    if(pos >= 0){
        Remove(pos); 
    }
}
/*
g++ -std=gnu++17 -O2 -fsigned-char -o grader grader.cpp ancientmachine.cpp Bruno.cpp
6
Y Z Y Z Y Z
8
X Y X Z Y X Y Z

48
X X Y Y Z Z Y X Y X Z Y X X Y Y Z Z Y X Y X Z Y X X Y Y Z Z Y X Y X Z Y X X Y Y Z Z Y X Y X Z Y

3
X X X

3
Y Y Y

3
Z Z Z

3
X Y Z

15
Y X Z Z X Y X Z Y Z X Y X Y Z

20
X X Y Y Z Z X Y Z X Y Z X X Y Z X Y Z X

25
Z Y X X Y Z Z Y X X Z Y X Y Z X Z Y X X Y Z Y X Z

4
X Z Y Z

906
Z Z X X Y Y Z X Y Z X X Y Z X Y Z X X Y Z X Y Z Z Y X X Z Y X Y Z X Y Z X Y X X X Y Z X Y Z X X Y Z Z Y X X Z Y X Y Z X Y Z X X Y Z X Y Z Z X
X Y Z Z Y X X Z Y X Y Z X X Y Z X Y Z X Y Z Z Y X X Z Y X Y Z X Y Z X X Y Z X Y Z Z X Y X X Y Z Y Z X X Y Y Z Z X Y Z X Y Z X X Y Z X Y Z X X
X Y Z Z Y X X Z Y X Y Z X X Y Z X Y Z X Y Z Z Y X X Z Y X Y Z X Y Z X X Y Z X Y Z Z X Y X X Y Z Y Z Y X Z Z X Y X Z Y Z X Y X Y Z X Y Z X X Y 
Z X Y Z Z Y X X Z Y X Y Z X Y Z X X Y Z X Y Z Z X Y X X Y Z X Y Z Z X Y Z Y X Y Z Z Y X X Z Y X Y Z X X Y Z X Y Z X Y Z Z Y X X Z Y X Y Z X Y 
Z X X Y Z X Y Z Z X Y X X Y Z Y Z Z Z X X Y Y Z X Y Z X X Y Z X Y Z X X Y Z X Y Z Z Y X X Z Y X Y Z X Y Z X Y X X X Y Z X Y Z X X Y Z Z Y X X Z Y X Y Z X Y Z X X Y Z X Y Z Z X
X Y Z Z Y X X Z Y X Y Z X X Y Z X Y Z X Y Z Z Y X X Z Y X Y Z X Y Z X X Y Z X Y Z Z X Y X X Y Z Y Z X X Y Y Z Z X Y Z X Y Z X X Y Z X Y Z X X
X Y Z Z Y X X Z Y X Y Z X X Y Z X Y Z X Y Z Z Y X X Z Y X Y Z X Y Z X X Y Z X Y Z Z X Y X X Y Z Y Z Y X Z Z X Y X Z Y Z X Y X Y Z X Y Z X X Y 
Z X Y Z Z Y X X Z Y X Y Z X Y Z X X Y Z X Y Z Z X Y X X Y Z X Y Z Z X Y Z Y X Y Z Z Y X X Z Y X Y Z X X Y Z X Y Z X Y Z Z Y X X Z Y X Y Z X Y 
Z X X Y Z X Y Z Z X Y X X Y Z Y Z Z Z X X Y Y Z X Y Z X X Y Z X Y Z X X Y Z X Y Z Z Y X X Z Y X Y Z X Y Z X Y X X X Y Z X Y Z X X Y Z Z Y X X Z Y X Y Z X Y Z X X Y Z X Y Z Z X
X Y Z Z Y X X Z Y X Y Z X X Y Z X Y Z X Y Z Z Y X X Z Y X Y Z X Y Z X X Y Z X Y Z Z X Y X X Y Z Y Z X X Y Y Z Z X Y Z X Y Z X X Y Z X Y Z X X
X Y Z Z Y X X Z Y X Y Z X X Y Z X Y Z X Y Z Z Y X X Z Y X Y Z X Y Z X X Y Z X Y Z Z X Y X X Y Z Y Z Y X Z Z X Y X Z Y Z X Y X Y Z X Y Z X X Y 
Z X Y Z Z Y X X Z Y X Y Z X Y Z X X Y Z X Y Z Z X Y X X Y Z X Y Z Z X Y Z Y X Y Z Z Y X X Z Y X Y Z X X Y Z X Y Z X Y Z Z Y X X Z Y X Y Z X Y 
Z X X Y Z X Y Z Z X Y X X Y Z Y Z Z Z Z Z

50
X Y Z Z Y X X Z Y X Y Z X X Y Z X Y Z X Y Z Z Y X X Z Y X Y Z X Y Z X X Y Z X Y Z Z X Y X X Y Z Y Z

60
Y X Z Z X Y X Z Y Z X Y X Y Z X Y Z X X Y Z X Y Z Z Y X X Z Y X Y Z X Y Z X X Y Z X Y Z Z X Y X X Y Z X Y Z Z X Y Z Y X

195
X X Y Z X Y Z X X Y Z Z Y X X Z Y X Y Z X Y Z X X Y Z X Y Z Z Y X X Z Y X Y Z X Y Z X 
X Y Z X Y Z Z X Y X X Y Z X Y Z Z X Y Z Y X Z X Y Z X X Y Z Z Y X X X Y Z X Y Z X X Y 
Z Z Y X X Z Y X Y Z X Y Z X X Y Z X Y Z Z Y X X Z Y X Y Z X Y Z X X Y Z X Y Z Z X Y X 
X Y Z X Y Z Z X Y Z Y X Z X Y Z X X Y Z Z Y X Z Z Z X X X Y Y Y Z Z Z X X X Y Y Y Z Z 
Z X X X Y Y Y Z Z Z X X X Y Y Y Z X X Y Z X Y Z X X Y Z X Y Z Z Y X X Z Y X Y Z X Y Z X Y X X

45
Z Z Z X X X Y Y Y Z Z Z X X X Y Y Y Z Z Z X X X Y Y Y Z Z Z X X X Y Y Y

16
X X X X X X X X X X X X X X Y Z

*/

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