Submission #651435

#	Time	Username	Problem	Language	Result	Execution time	Memory
651435		rainboy	Broken Device 2 (JOI22_device2)	C++17	100 / 100	78 ms	2928 KiB

Anna

/* https://www.ioi-jp.org/camp/2022/2022-sp-tasks/contest3/device2-review.pdf */
/* https://oj.uz/submission/544506 */
#include "Anna.h"
#include <assert.h>
#include <vector>

using namespace std;

typedef vector<int> vi;

const long long N = 1000000000000000000LL;
const int L = 140;

namespace {
	long long dp[L + 1];
}

int Declare() {
	dp[1] = 1, dp[2] = 1, dp[3] = 2;
	for (int l = 4; l <= L; l++)
		dp[l] = dp[l - 3] + dp[l - 2] + 1;
	long long n = 0;
	for (int l = 1; l <= L; l++)
		n += dp[l] * 2;
	assert(n > N);
	return L;
}

pair<vi, vi> Anna(long long x) {
	x--;
	int a = x % 2;
	x /= 2;
	int l = 1;
	while (x >= dp[l])
		x -= dp[l++];
	vi aa(l, 0), bb(l, 0);
	for (int i = 0; i < l; i++)
		aa[i] = (a + i) % 2;
	bb[0] = a;
	int i = 1;
	while (i < l)
		if (x == 0)
			bb[i] = bb[i - 1] ^ 1, i++;
		else if (x <= dp[l - i - 1])
			x--, bb[i] = bb[i + 1] = bb[i - 1], i += 2;
		else
			x -= dp[l - i - 1] + 1, bb[i] = bb[i + 1] = bb[i + 2] = bb[i - 1] ^ 1, i += 3;
	return make_pair(aa, bb);
}

Bruno

/* https://www.ioi-jp.org/camp/2022/2022-sp-tasks/contest3/device2-review.pdf */
/* https://oj.uz/submission/544506 */
#include "Bruno.h"
#include <assert.h>
#include <vector>

using namespace std;

typedef vector<int> vi;

const long long N = 1000000000000000000LL;
const int L = 140;

namespace {
	long long dp[L + 1];
	bool init = false;
}

long long Bruno(vi cc) {
	if (!init) {
		init = true;
		dp[1] = 1, dp[2] = 1, dp[3] = 2;
		for (int l = 4; l <= L; l++)
			dp[l] = dp[l - 3] + dp[l - 2] + 1;
		long long n = 0;
		for (int l = 1; l <= L; l++)
			n += dp[l] * 2;
		assert(n > N);
	}
	int l = cc.size() / 2;
	long long x = 1;
	for (int l_ = 1; l_ < l; l_++)
		x += dp[l_] * 2;
	if (cc[0] == 1) {
		for (int i = 0; i < l * 2; i++)
			cc[i] ^= 1;
		x++;
	}
	int d = 0, c = 0;
	for (int i = 1, j = 1; j < l * 2; j++) {
		if (cc[j] == 0)
			d++;
		else
			d--;
		if (d >= 2) {
			if (c == 0)
				x += 2, i += 2;
			else
				x += (dp[l - i - 1] + 1) * 2, i += 3, c = 0;
			d = 0;
		} else if (d <= -2) {
			if (c == 1)
				x += 2, i += 2;
			else
				x += (dp[l - i - 1] + 1) * 2, i += 3, c = 1;
			d = 0;
		}
	}
	return x;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 3 / 3
• Subtask 4: 12 / 12
• Subtask 5: 15 / 15
• Subtask 6: 60 / 60