oj.uz

Submission #387981

# Submission time Handle Problem Language Result Execution time Memory
387981 2021-04-09T15:45:45 Z keko37 Ancient Machine (JOI21_ancient_machine) C++17
0 / 100
 77 ms 8392 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 = N - 1; i >= 0; i--) {
		if (i == lef || i == rig) continue;
		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 Correct 2 ms 484 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 496 KB Output is correct
5 Correct 2 ms 484 KB Output is correct
6 Correct 4 ms 484 KB Output is correct
7 Correct 2 ms 484 KB Output is correct
8 Correct 2 ms 564 KB Output is correct
9 Incorrect 2 ms 492 KB Wrong Answer [3]
10 Halted 0 ms 0 KB -

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 8364 KB Output is correct
2 Correct 74 ms 8364 KB Output is correct
3 Correct 68 ms 8356 KB Output is correct
4 Correct 72 ms 8268 KB Output is correct
5 Correct 70 ms 8344 KB Output is correct
6 Correct 67 ms 8216 KB Output is correct
7 Correct 73 ms 8272 KB Output is correct
8 Correct 77 ms 8296 KB Output is correct
9 Correct 72 ms 8156 KB Output is correct
10 Correct 69 ms 8280 KB Output is correct
11 Correct 71 ms 8296 KB Output is correct
12 Correct 74 ms 8324 KB Output is correct
13 Correct 69 ms 7908 KB Output is correct
14 Correct 76 ms 8392 KB Output is correct
15 Correct 66 ms 8340 KB Output is correct
16 Correct 62 ms 8216 KB Output is correct
17 Incorrect 57 ms 8264 KB Wrong Answer [3]
18 Halted 0 ms 0 KB -