Submission #1150677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150677		yeyso	Ancient Machine (JOI21_ancient_machine)	C++20	0 / 100	38 ms	6812 KiB

Anna

#include "Anna.h"
using namespace std;
#include <bits/stdc++.h>
#define lint __uint128_t
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(100, 0);
    z[0] = 1;
    z[1] = 2;
    for(int i = 2; i < 100; i ++){
        z[i] = z[i-1] + z[i-2];
    }
    int pos = -1;
    vector<int> A;
    for(int i = 0; i < S.size(); i ++){
        if(S[i] != 'X'){
            A.push_back(0);
        } else {
            A.push_back(1);
            pos = i;
            break;
        }
    }
    // REMEMBER THIS CASE!
    if(pos == -1) return;
    int cur = pos;
    for(int i = pos + 1; i < N; i ++){
        if(S[i] == 'Z'){
            if(A.size() > 0){
                if(A[i-1] == 0){
                    A.push_back(1);
                } else {
                    A.push_back(0);
                }
            } else {
                A.push_back(1);
            }
        } else {
            A.push_back(0);
        }
    }
    /*for(int i = 0; i < A.size(); i ++){
        cout << A[i] << " ";
    } cout << "\n\n\n";*/
    vector<int> message;
    for(int i = 0; i < A.size(); i += 100){
        lint res = 0;
        for(int j = i; j < min((int)(i + 100), (int)A.size()); j ++){
            if(A[j] == 1){
                res += z[j % 100];
            }
        }
        vector<int> packet;
        to_binary(res, packet);
        /*for(int i = 0; i < packet.size(); i ++){
            message.push_back(packet[i]);
        }*/
        /*for(int j = packet.size(); j < 70; j ++){
            message.push_back(0);
        }*/
        for(int j = packet.size() - 1; j >= 0; j --){
            message.push_back(packet[j]);
            //message.push_back(1);
        }
        for(int j = packet.size(); j < 70; j ++){
            message.push_back(0);
        }
    }
    //cout << message.size() << " | ";
    for(int i = 0; i < message.size(); i ++){
        //cout << message[i] << " ";
        //Send(message[i]);
    }
    for(int i = 0; i < A.size(); i ++){
        Send(A[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

156
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>
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(100, 0);
    z[0] = 1;
    z[1] = 2;
    for(int i = 2; i < 100; i ++){
        z[i] = z[i-1] + z[i-2];
    }
    //cout << "\n\n";
    for(int i = 0; i < A.size(); i += 70){
        lint cur = 0;
        for(int j = i; j < min((int)A.size(), (int)(i + 70)); j ++){
            //cout << A[j] << " ";
            cur += (lint)A[j] * ((lint)1 << (j % 70));
        }
        //cout << plint(cur) << " | ";
        vector<int> output;
        for(int j = z.size() - 1; j >= 0; j --){
            if(cur >= z[j]){
                output.push_back(1);
                //cout << plint(z[j]) << " ";
                cur -= z[j];
            } else {
                output.push_back(0);
            }
        }

        for(int j = output.size() - 1; j >= 0; j --){
            //cout << output[j] << " ";
            A2.push_back(output[j]);
        } //cout << "\n\n";
        //cout << plint(cur);
    }
    /*for(int i = 0; i < A2.size(); i ++){
        cout << A2[i] << " ";
    }*/
    A2 = A;
    int pos = -1;
    for(int i = 0; i < A2.size(); i ++){
        if(A2[i] == 0){
            Remove(i);
        } else {
            pos = i;
            break;
        }
    }
    if(pos == -1) return;
    int cur = pos;
    for(int i = pos + 1; i < A2.size(); 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

30
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

40
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

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: 0 / 5
• Subtask 2: 0 / 95