Submission #655899

#	Time	Username	Problem	Language	Result	Execution time	Memory
655899		gs12117	Broken Device 2 (JOI22_device2)	C++17	100 / 100	80 ms	3016 KiB

Anna

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <random>

int Declare() {
	int max_m = 139;
	return max_m;
}

std::pair<std::vector<int>, std::vector<int> > Anna(long long A) {
	int max_m = 139;
	long long int dp[200];
	for (int i = 0; i < max_m; i++) {
		if (i < 5)dp[i] = i + 1;
		else dp[i] = dp[i - 2] + dp[i - 3];
	}
	int sz = 0;
	for (int i = max_m - 3; i >= 0; i--) {
		if (A < dp[i] * 4) {
			sz = i;
			break;
		}
		A -= dp[i] * 4;
	}
	int invt = 0;
	if (A >= dp[sz] * 2) {
		A -= dp[sz] * 2;
		invt = 1;
	}
	std::vector<int> X;
	std::vector<int> Y;
	for (int i = 0; i < sz + 3; i++) {
		Y.push_back((sz + i) % 2); // last Y[sz+2]=0
	}
	if (A >= dp[sz]) {
		A -= dp[sz];
		X.push_back(1);
		X.push_back(1);
	}
	else {
		X.push_back(0);
		X.push_back(0);
	}
	int p = sz;
	while (1) {
		if (p < 5) {
			for (int i = 0; i < p; i++) {
				if (i < A)X.push_back(1);
				else X.push_back(0);
			}
			break;
		}
		else {
			if (A >= dp[p - 2]) {
				A -= dp[p - 2];
				X.push_back(1 - X[X.size() - 1]);
				p--;
			}
			X.push_back(X[X.size() - 1]);
			X.push_back(X[X.size() - 1]);
			p -= 2;
		}
	}
	X.push_back(0);
	if (invt == 1) {
		for (int i = 0; i < sz + 3; i++) {
			X[i] = 1 - X[i];
			Y[i] = 1 - Y[i];
		}
	}
	return make_pair(X, Y);
}

Bruno

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <random>

long long Bruno(std::vector<int> u) {
	int max_m = 139;
	long long int dp[200];
	for (int i = 0; i < max_m; i++) {
		if (i < 5)dp[i] = i + 1;
		else dp[i] = dp[i - 2] + dp[i - 3];
	}
	int sz = u.size() / 2 - 3;
	long long int ans = 0;
	for (int i = max_m - 3; i >= 0; i--) {
		if (i == sz) {
			break;
		}
		ans += dp[i] * 4;
	}
	std::vector<int> v = u;
	if (u[u.size() - 1] == 1) {
		ans += dp[sz] * 2;
		for (int i = 0; i < v.size(); i++) {
			v[i] = 1 - v[i];
		}
	}
	int sumv = 0;
	for (int i = 0; i < v.size(); i++) {
		sumv += v[i];
	}
	sumv -= (sz + 3) / 2;
	int curmax = 0;
	int curmin = 0;
	int curv = 0;
	if (sz % 2 == 1) {
		curmax = 1;
	}
	else {
		curmin = -1;
	}
	int p = 0;
	for (; p < v.size();) {
		curv += 2 * v[p] - 1;
		p++;
		if (curv > curmax || curv < curmin) {
			break;
		}
	}
	int lastv = 0;
	int szleft = sz;
	if (curv > curmax) {
		ans += dp[sz];
		lastv = 1;
		sumv -= 2;
	}
	curmax = curv + 1;
	curmin = curv - 1;
	while (szleft >= 5) {
		curv += 2 * v[p] - 1;
		p++;
		if (curv > curmax) {
			if (lastv == 0) {
				ans += dp[szleft - 2];
				szleft--;
				sumv--;
			}
			lastv = 1;
			curmax = curv + 1;
			curmin = curv - 1;
			szleft -= 2;
			sumv -= 2;
		}
		else if (curv < curmin) {
			if (lastv == 1) {
				ans += dp[szleft - 2];
				szleft--;
			}
			lastv = 0;
			curmax = curv + 1;
			curmin = curv - 1;
			szleft -= 2;
		}
	}
	ans += sumv;
	return ans;
}

Compilation message (stderr)

Bruno.cpp: In function 'long long int Bruno(std::vector<int>)':
Bruno.cpp:24:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   for (int i = 0; i < v.size(); i++) {
      |                   ~~^~~~~~~~~~
Bruno.cpp:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
Bruno.cpp:43:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for (; p < v.size();) {
      |         ~~^~~~~~~~~~

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