oj.uz

Submission #387980

# Submission time Handle Problem Language Result Execution time Memory
387980 2021-04-09T15:43:12 Z keko37 Ancient Machine (JOI21_ancient_machine) C++17
0 / 100
 71 ms 8276 KB 
#include<bits/stdc++.h>
#include "Anna.h"
#include <vector>

using namespace std;

typedef long long llint;

const int MAXN = 90;
const int SIZ = 63;

llint fib[MAXN];

int get_bits (llint val) {
	int res = 0;
	llint pot = 1;
	for (int i = 0; i < 50; i++) {
		if (val & pot) res = i + 1;
		pot *= 2;
	}
	return res;
}

void precompute () {
	fib[0] = 0; fib[1] = 1;
	for (int i = 2; i < MAXN; i++) {
		fib[i] = fib[i - 1] + fib[i - 2];
	}
}

void send_num (llint val, int br) {
	llint pot = 1;
	for (int i = 0; i < br; i++) {
		if (val & pot) Send(1); else Send(0);
		pot *= 2;
	}
}

llint compress (vector <int> v) {
	int n = 0;
	for (auto x : v) n += x;
	llint res = 1;
	for (auto x : v) {
		if (x == 1) {
			n--;
		} else {
			res += fib[n];
			n -= 2;
		}
	}
	return res;
}

void Anna (int N, vector <char> S) {
	precompute();
	int lef = N, rig = N;
	for (int i = 0; i < N; i++) {
		if (S[i] == 'X') {
			lef = i;
			break;
		}
	}
	for (int i = N-1; i >= 0; i--) {
		if (S[i] == 'Z') {
			rig = i;
			break;
		}
	}
	send_num(lef, 17);
	send_num(rig, 17);
	
	vector <int> r((SIZ + 1) / 2, 2);
	int bits = get_bits(compress(r));
	
	vector <int> v;
	for (int i = 0; i < N; i++) {
		if (i + 1 < N && S[i] == 'Y' && S[i + 1] == 'X') {
			v.push_back(2);
			i++;
		} else {
			v.push_back(1);
		}
	}
	vector <int> tmp;
	int sum = 0;
	for (auto x : v) {
		tmp.push_back(x);
		sum += x;
		if (sum >= SIZ) {
			if (sum == SIZ) tmp.push_back(1);
			send_num(compress(tmp), bits);
			tmp.clear();
			sum = 0;
		}
	}
	if (!tmp.empty()) {
		while (sum < SIZ + 1) {
			tmp.push_back(1);
			sum++;
		}
		send_num(compress(tmp), bits);
	}
}





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

using namespace std;

typedef long long llint;

const int MAXN = 90;
const int SIZ = 63;

llint fib_bruno[MAXN];
int a_pos;
vector <int> a;

int get_bits_bruno (llint val) {
	int res = 0;
	llint pot = 1;
	for (int i = 0; i < 50; i++) {
		if (val & pot) res = i + 1;
		pot *= 2;
	}
	return res;
}

void precompute_bruno () {
	fib_bruno[0] = 0; fib_bruno[1] = 1;
	for (int i = 2; i < MAXN; i++) {
		fib_bruno[i] = fib_bruno[i - 1] + fib_bruno[i - 2];
	}
}

llint get_num (int br) {
	llint res = 0;
	llint pot = 1;
	for (int i = 0; i < br; i++) {
		res += pot * a[a_pos];
		a_pos++;
		pot *= 2;
	}
	return res;
}

llint compress_bruno (vector <int> v) {
	int n = 0;
	for (auto x : v) n += x;
	llint res = 1;
	for (auto x : v) {
		if (x == 1) {
			n--;
		} else {
			res += fib_bruno[n];
			n -= 2;
		}
	}
	return res;
}

vector <int> decompress (llint val) {
	vector <int> v;
	int n = SIZ + 1;
	while (n > 0) {
		if (val > fib_bruno[n]) {
			val -= fib_bruno[n];
			v.push_back(2);
			n -= 2;
		} else {
			v.push_back(1);
			n--;
		}
	}
	return v;
}

void ispis (vector <int> v) {
	for (auto x : v) cout << x << " "; cout << endl;
}

void Bruno (int N, int L, vector <int> A) {
	a = A;

	precompute_bruno();
	vector <int> r((SIZ + 1) / 2, 2);
	int bits = get_bits_bruno(compress_bruno(r));
	
	int lef = get_num(17);
	int rig = get_num(17);
	
	vector <int> v;
	while (a_pos < L) {
		llint val = get_num(bits);
		vector <int> tmp = decompress(val);
		if (tmp.back() == 1) tmp.pop_back();
		for (auto x : tmp) {
			if (x == 1) v.push_back(1);
			if (x == 2) v.push_back(0), v.push_back(0);
		}
	}
	
	v[lef] = 0; v[rig] = 0;
	
	for (int i = 0; i < N; i++) {
		if (v[i] == 1) Remove(i);
	}
	for (int i = rig - 1; i >= lef + 1; i--) {
		if (v[i] == 0) Remove(i);
	}
	Remove(lef); Remove(rig);
}

Compilation message

Bruno.cpp: In function 'void ispis(std::vector<int>)':
Bruno.cpp:76:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   76 |  for (auto x : v) cout << x << " "; cout << endl;
      |  ^~~
Bruno.cpp:76:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   76 |  for (auto x : v) cout << x << " "; cout << endl;
      |                                     ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 492 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 8264 KB Output is correct
2 Incorrect 63 ms 8276 KB Wrong Answer [5]
3 Halted 0 ms 0 KB -