Submission #647919

#	Time	Username	Problem	Language	Result	Execution time	Memory
647919		rainboy	Broken Device 2 (JOI22_device2)	C++17	13 / 100	2091 ms	25924 KiB

Anna

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

using namespace std;

const int L = 2000;

typedef vector<int> vi;

namespace {
	int f(int l) {
		if (l == 1)
			return 3;
		if (l == 2)
			return 6;
		return (l * 2 - 3) * 4;
	}

	int g(int l, int k) {
		int n = 0;
		if (k >= 4)
			n++;
		if (l * 2 - k >= 4)
			n++;
		if (k >= 2 && l * 2 - k >= 2)
			n += 2;
		if (n == 0)
			n = 1;
		return n;
	}
}

int Declare() {
	return L;
}

pair<vi, vi> Anna(long long x) {
	x--;
	int l = 1;
	while (x >= f(l))
		x -= f(l++);
	int k = 0;
	while (x >= g(l, k))
		x -= g(l, k++);
	vi aa(l, 0), bb(l, 0);
	if (k >= 4 && x-- == 0) {
		aa[0] = bb[0] = 1;
		aa[l - 1] = bb[l - 1] = 1;
		if (k <= l + 2)
			for (int i = 1; i <= k - 4; i++)
				aa[i] = 1;
		else {
			for (int i = 1; i <= l - 2; i++)
				aa[i] = 1;
			for (int i = 1; i <= k - l - 2; i++)
				bb[i] = 1;
		}
	} else if (l * 2 - k >= 4 && x-- == 0) {
		aa[0] = bb[0] = 0;
		aa[l - 1] = bb[l - 1] = 0;
		if (k <= l - 2)
			for (int i = 1; i <= k; i++)
				aa[i] = 1;
		else {
			for (int i = 1; i <= l - 2; i++)
				aa[i] = 1;
			for (int i = 1; i <= k - l + 2; i++)
				bb[i] = 1;
		}
	} else if (k >= 2 && l * 2 - k >= 2 && x-- == 0) {
		aa[0] = bb[0] = 0;
		aa[l - 1] = bb[l - 1] = 1;
		if (k <= l)
			for (int i = 1; i <= k - 2; i++)
				aa[i] = 1;
		else {
			for (int i = 1; i <= l - 2; i++)
				aa[i] = 1;
			for (int i = 1; i <= k - l; i++)
				bb[i] = 1;
		}
	} else if (k >= 2 && l * 2 - k >= 2 && x-- == 0) {
		aa[0] = bb[0] = 1;
		aa[l - 1] = bb[l - 1] = 0;
		if (k <= l)
			for (int i = 1; i <= k - 2; i++)
				aa[i] = 1;
		else {
			for (int i = 1; i <= l - 2; i++)
				aa[i] = 1;
			for (int i = 1; i <= k - l; i++)
				bb[i] = 1;
		}
	} else {
		if (k <= l)
			for (int i = 0; i < k; i++)
				aa[i] = 1;
		else {
			for (int i = 0; i < l; i++)
				aa[i] = 1;
			for (int i = 0; i < k - l; i++)
				bb[i] = 1;
		}
	}
	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;

namespace {
	int f(int l) {
		if (l == 1)
			return 3;
		if (l == 2)
			return 6;
		return (l * 2 - 3) * 4;
	}

	int g(int l, int k) {
		int n = 0;
		if (k >= 4)
			n++;
		if (l * 2 - k >= 4)
			n++;
		if (k >= 2 && l * 2 - k >= 2)
			n += 2;
		if (n == 0)
			n = 1;
		return n;
	}
}

long long Bruno(vi cc) {
	int l = cc.size() / 2, k = 0;
	for (int i = 0; i < l * 2; i++)
		if (cc[i] == 1)
			k++;
	int x = 1;
	for (int l_ = 1; l_ < l; l_++)
		x += f(l_);
	for (int k_ = 0; k_ < k; k_++)
		x += g(l, k_);
	if (g(l, k) > 1) {
		if (cc[0] == 1 && cc[l * 2 - 1] == 1)
			return x;
		if (k >= 4)
			x++;
		if (cc[0] == 0 && cc[l * 2 - 1] == 0)
			return x;
		if (l * 2 - k >= 4)
			x++;
		if (cc[0] == 0 && cc[l * 2 - 1] == 1)
			return x;
		if (k >= 2 && l * 2 - k >= 2)
			x++;
	}
	return x;
}

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