Submission #647962

#	Time	Username	Problem	Language	Result	Execution time	Memory
647962		rainboy	Broken Device 2 (JOI22_device2)	C++17	80 / 100	91 ms	3460 KiB

Anna

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

using namespace std;

typedef vector<int> vi;

const int L = 180;

namespace {
	long long f(int l) {
		return 1LL << (l + 2) / 3;
	}
}

int Declare() {
	return L;
}

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

Bruno

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

using namespace std;

typedef vector<int> vi;

const int L = 180;

namespace {
	long long f(int l) {
		return 1LL << (l + 2) / 3;
	}
}

int dd[L * 2];

long long Bruno(vi cc) {
	int l = cc.size() / 2;
	long long x = 1;
	for (int l_ = 1; l_ < l; l_++)
		x += f(l_);
	int k = 0;
	for (int i = 0; i < l * 2; i++)
		if (cc[i] == 1)
			k++;
	k -= l / 2;
	for (int i = 0, d = 0; i < l * 2; i++)
		if (cc[i] == 0)
			dd[i] = d++;
		else
			dd[i] = --d;
	vi aa;
	int l_ = l, i = 0, d = 0;
	while (1) {
		if (k == 0) {
			while (l_ > 0)
				aa.push_back(0), l_--;
			break;
		}
		if (k == l_) {
			while (l_ > 0)
				aa.push_back(1), l_--;
			break;
		}
		while (1)
			if (dd[i] == d * 3 + 2) {
				aa.push_back(0), aa.push_back(0), aa.push_back(0);
				l_ -= 3, d++;
				break;
			} else if (dd[i] == d * 3 - 2) {
				aa.push_back(1), aa.push_back(1), aa.push_back(1);
				k -= 3, l_ -= 3, d--;
				break;
			} else
				i++;
	}
	for (int i = 0; i < l; i += 3)
		if (aa[i])
			x += 1LL << i / 3;
	return x;
}

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