Submission #1179928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179928		khusanov45	Ancient Machine (JOI21_ancient_machine)	C++17	99 / 100	43 ms	6472 KiB

Anna

#include "Anna.h"
#include <vector>
#include <iostream>

using namespace std;

#define ll long long

bool DEBUG1 = false;

int bitlen1 = 42;
int sectionLength = 60;

namespace {

vector<ll> fib;

void initFib() {
    fib.push_back(1);
    fib.push_back(1);

    for (int i = 2; i <= sectionLength+2; ++i){
        fib.push_back(fib[i-2] + fib[i-1]);
    }
}
//0000000000001010001010100001010000010001001000001000001010000001
//0000000000001010001010100001010000010001001000001000001010000010
ll handleArray(string& b, int l, int r) {
    ll score = 0;

    for (int i = l; i < r; ++i){
        score += ((ll)b[i]) * (ll)fib[r-i];
    }

    return score;
}

void sendSignals(ll x){
    for (int i = bitlen1-1; i >= 0; --i){
        Send((x >> i) & 1);
    }
}
  
}

void Anna(int N, vector<char> S) {
   

    initFib();

    int len = ((N + sectionLength-1) / sectionLength)*sectionLength;

    string b(len, 0);

    int i = -1;
    while (++i < N && S[i] != 'X');

    if (i == N){
        Send(1);
        return;
    }

    //i: S[i] = X. send index

    for (int l = 0; l < 20; ++l ){
        Send ((i >> l) & 1);
    }

    for (; i < N; ++i){
        if (i + 1 < N && S[i] == S[i+1]){
            continue;
        }
        b[i] = (S[i] == 'Z')?1:0;
        
    }

    


    auto hashValue = std::hash<std::string>{}(b); 
    for (int i = 0; i != 64; ++i){
        Send((hashValue >> i) & 1);
    }
    if (DEBUG1){
        std::cout << "sent hash " << hashValue << endl;
        std::cout << "code" << endl;
        int i = 0;
        for (char c : b){
            
            cout << int(c);
            if (++i % sectionLength == 0) {
                cout << endl;
            }
        }
        cout << endl;
    } 

    for (int l = 0; l < N; l += sectionLength){
        ll permutation = handleArray(b, l, l+sectionLength);
        if (DEBUG1){
            cout << "Anna = " << permutation << endl;
        }
        sendSignals(permutation);
    }
    
    

}

Bruno

#include "Bruno.h"
#include <vector>
#include <iostream>

using namespace std;

#define ll long long

bool DEBUG = false;
namespace {

int bitlen = 42;
int sectionlength = 60;

vector<ll> fib;

void initFib() {
	fib.push_back(1);
	fib.push_back(1);

	for (int i = 2; i <= sectionlength+2; ++i){
		fib.push_back(fib[i-2] + fib[i-1]);
	}
}

ll getNumber(vector<int> & a, int start){
	ll ans = 0;	

	for (int i = start; i < start + bitlen; ++i){
		ans <<= 1;
		ans += a[i];
	}

	return ans;
}

//0000000000001010001010100001010000010001001000001000001010000001
//0000000000001010001010100001010000010001001000001000001010000010
void deriveSequence(ll number, string & result){
	for (int i = sectionlength; i >= 1; --i){
		if (fib[i] <= number){
			number -= fib[i];
			result += char(1);
		}
		else{
			result += char(0);
		}		
	}	
}

}
void Bruno(int N, int L, std::vector<int> A) {
	if (DEBUG){
		cout << "L = " << L << endl;
	}
	
	if (L == 1){
		for (int i = 0; i < N; ++i){
			Remove(i);
		}
		return;
	}
	initFib();
	
	int id = 0;

	ll indexX = 0;
	for (;id < 20; ++id){
		indexX |= (A[id] << id);
	}

	std::size_t hashValue = 0;
	for (int i = 0; i != 64; ++i){
		hashValue |= ((size_t)A[id++] << i);
		
	}

	if (DEBUG){
		cout << "get index = " << indexX << endl;
		cout << "id = " << id << endl;
	}

	string result;
	for (;id < L; id += bitlen){
		ll number = getNumber(A, id);
		if (DEBUG){
			cout << "Bruno number = " << number << endl;
		}
		deriveSequence(number, result);
	}

	if (DEBUG) {
		std::cout << "get hash = " << hashValue << endl;
		for (int i = 0; i != sectionlength; ++i){
			std::cout << A[sectionlength-1-i];
		}
		cout << endl;
		cout << "Code got " << endl;
		int i = 0;
		for (char c : result){
			
			cout << int(c);
			if (++i % sectionlength == 0){
				cout << endl;
			}
		}
		cout << endl;		
	}

	size_t getHash = std::hash<std::string>{}(result);
	if (DEBUG) {
		cout << "Cal hash = " << getHash << endl;	
	}

	if (getHash != hashValue){
		Remove(-1);
		if (DEBUG) {
			cout << "Get wrong data: " << hashValue << " " << getHash << endl;

		}
		return;
	}


	vector<int> ones;
	ones.push_back(indexX);
	for (int i = 0; i < result.size(); ++i){
		if (result[i] == 1){
			ones.push_back(i);
		}
	}
	// PreX
	for (int i =0; i != ones.front();++i){
		Remove(i);
	}

	for (int i = 1; i < ones.size(); ++i){
		for (int j = ones[i]-1; j > ones[i-1]; --j){
			Remove(j);
		}
		Remove(ones[i]);
	}

	Remove(ones[0]);

	for (int j = ones.back()+1; j < N; ++j){
		Remove(j);
	}
}

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