Submission #1101171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101171		rainboy	Flights (JOI22_flights)	C++17	32 / 100	211 ms	1904 KiB

Ali

#include "Ali.h"
#include <cstring>
#include <string>
#include <vector>

using namespace std;

typedef vector<int> vi;

namespace Ali {
	const int N = 10000, K = 20;
	const int B = 7, M = (N + B - 1) / B, L = 14;	/* L = ceil(log2(N)) */

	int min(int a, int b) { return a < b ? a : b; }

	void encode(string &aa, int i_, int n, int x) {
		for (int i = 0; i < n; i++)
			aa[i_ + i] = (x >> i & 1) + '0';
	}

	int decode(string &aa, int i_, int n) {
		int x = 0;
		for (int i = 0; i < n; i++)
			if (aa[i_ + i] == '1')
				x |= 1 << i;
		return x;
	}

	void decode2(int n, int x, int &i, int &j) {
		i = 0;
		while (x >= n - i)
			x -= n - i++;
		j = i + x;
	}

	int ej[N][3], eo[N], n;

	void append(int i, int j) {
		ej[i][eo[i]++] = j;
	}

	void init(vi ii, vi jj, int n_) {
		n = n_;
		memset(eo, 0, n * sizeof *eo);
		for (int h = 0; h < n - 1; h++)
			append(ii[h], jj[h]), append(jj[h], ii[h]);
		for (int i = 0; i < n; i++)
			SetID(i, i);
	}

	int dd[N];

	void dfs(int p, int i, int d) {
		dd[i] = d;
		for (int o = eo[i]; o--; ) {
			int j = ej[i][o];
			if (j != p)
				dfs(i, j, d + 1);
		}
	}

	string send(string bb) {
		int u_, v_; decode2(M, decode(bb, 0, K), u_, v_);
		int ul = u_ * B, ur = min((u_ + 1) * B, n), vl = v_ * B, vr = min((v_ + 1) * B, n);
		string cc((ur - ul) * (vr - vl) * L, '?');
		for (int u = ul; u < ur; u++) {
			dfs(-1, u, 0);
			for (int v = vl; v < vr; v++)
				encode(cc, ((u - ul) * (vr - vl) + (v - vl)) * L, L, dd[v]);
		}
		return cc;
	}
}

void Init(int n, vi ii, vi jj) {
	Ali::init(ii, jj, n);
}

string SendA(string bb) {
	return Ali::send(bb);
}

Benjamin

#include "Benjamin.h"
#include <string>
#include <vector>

using namespace std;

typedef vector<int> vi;

namespace Benjamin {
	const int N = 10000, K = 20;
	const int B = 7, M = (N + B - 1) / B, L = 14;	/* L = ceil(log2(N)) */

	int min(int a, int b) { return a < b ? a : b; }

	void encode(string &aa, int i_, int n, int x) {
		for (int i = 0; i < n; i++)
			aa[i_ + i] = (x >> i & 1) + '0';
	}

	int decode(string &aa, int i_, int n) {
		int x = 0;
		for (int i = 0; i < n; i++)
			if (aa[i_ + i] == '1')
				x |= 1 << i;
		return x;
	}

	int encode2(int n, int i, int j) {
		return i * (n * 2 - i + 1) / 2 + j - i;
	}

	int n, u, v, u_, v_;

	string send(int n_, int u__, int v__) {
		n = n_, u = u__, v = v__;
		if (u > v) {
			int tmp;
			tmp = u, u = v, v = tmp;
		}
		u_ = u / B, v_ = v / B;
		string bb(K, '?');
		encode(bb, 0, K, encode2(M, u_, v_));
		return bb;
	}

	int answer(string aa) {
		int ul = u_ * B, vl = v_ * B, vr = min((v_ + 1) * B, n);
		return decode(aa, ((u - ul) * (vr - vl) + (v - vl)) * L, L);
	}
}

string SendB(int n, int u, int v) {
	return Benjamin::send(n, u, v);
}

int Answer(string aa) {
	return Benjamin::answer(aa);
}

Compilation message (stderr)

grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
   10 |   char _randmem[12379];
      |        ^~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 17 / 85