Submission #647940

#	Time	Username	Problem	Language	Result	Execution time	Memory
647940		rainboy	Broken Device 2 (JOI22_device2)	C++17	40 / 100	568 ms	24868 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 {
	long long f(int l) {
		return (long long) (l / 3 + 1) * ((l + 1) / 3 + 1) * ((l + 2) / 3 * 2 + 1);
	}
}

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);
	int l0 = l / 3, l1 = (l + 1) / 3, l2 = (l + 2) / 3;
	int kl = x % (l0 + 1), kr = x / (l0 + 1) % (l1 + 1), km = x / (l0 + 1) / (l1 + 1);
	for (int i = 0; i < kl; i++)
		aa[i] = bb[l0 - 1 - i] = 1;
	for (int i = l - 1; i >= l - kr; i--)
		aa[i] = bb[l - l1 + l - 1 - i] = 1;
	if (km <= l2)
		for (int i = 0; i < km; i++)
			aa[l0 + i] = 1;
	else {
		for (int i = 0; i < l2; i++)
			aa[l0 + i] = 1;
		for (int i = 0; i < km - l2; i++)
			bb[l0 + 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 {
	long long f(int l) {
		return (long long) (l / 3 + 1) * ((l + 1) / 3 + 1) * ((l + 2) / 3 * 2 + 1);
	}
}

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 l0 = l / 3;
	int l1 = (l + 1) / 3;
	int kl = 0;
	for (int i = 0; i < l0; i++)
		if (cc[i] == 1)
			kl++;
	int kr = 0;
	for (int i = l * 2 - 1; i >= l * 2 - l1; i--)
		if (cc[i] == 1)
			kr++;
	int km = 0;
	for (int i = 0; i < l * 2; i++)
		if (cc[i] == 1)
			km++;
	km -= (kl + kr) * 2;
	return x + ((long long) km * (l1 + 1) + kr) * (l0 + 1) + kl;
}

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