Submission #558039

#	Time	Username	Problem	Language	Result	Execution time	Memory
558039		DanShaders	Flights (JOI22_flights)	C++17	32 / 100	578 ms	1916 KiB

Ali

//bs:flags:grader.cpp
#include "Ali.h"
#include "Benjamin.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

namespace x = __gnu_pbds;
template <typename T>
using ordered_set = x::tree<T, x::null_type, less<T>, x::rb_tree_tag, x::tree_order_statistics_node_update>;

template <typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;

#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
#define x first
#define y second
using ll = long long;
using ld = long double;

const int N = 1e4 + 10;

int n;
vector<int> g[N];

void Init(int n_, vector<int> u, vector<int> v) {
	n = n_;
	for (int i = 0; i < n; ++i) {
		g[i].clear();
	}
	for (int i = 0; i < n - 1; ++i) {
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}
	for (int i = 0; i < n; ++i) {
		SetID(i, i);
	}
}

int get_forward(int x, int y) {
	return y * (y + 1) / 2 + x;
}

pair<int, int> get_backward(int num) {
	int lef = 0, rig = n;
	while (rig - lef > 1) {
		int mid = (lef + rig) / 2;
		if (mid * (mid + 1) / 2 <= num) {
			lef = mid;
		} else {
			rig = mid;
		}
	}
	return {num - lef * (lef + 1) / 2, lef};
}

int dfs(int u, int w, int p = -1) {
	if (u == w) {
		return 0;
	}
	for (int v : g[u]) {
		if (v != p) {
			int ans = dfs(v, w, u);
			if (ans != -1) {
				return ans + 1;
			}
		}
	}
	return -1;
}

string SendA(string s) {
	int msk = 0;
	for (int i = 0; i < 20; ++i) {
		msk |= (s[i] - '0') << (19 - i);
	}
	ostringstream oss;
	while (msk < get_forward(0, n)) {
		auto [x, y] = get_backward(msk);
		oss << bitset<14>(dfs(x, y));
		msk += (1 << 20);
	}
	return oss.str();
}

int x, y;

string SendB(int n_, int x_, int y_) {
	n = n_, x = x_, y = y_;
	if (x > y) {
		swap(x, y);
	}
	ostringstream oss;
	oss << bitset<20>(get_forward(x, y) % (1 << 20));
	return oss.str();
}

int Answer(string t) {
	int where = get_forward(x, y) / (1 << 20);
	int msk = 0;
	for (int i = 0; i < 14; ++i) {
		msk |= (t[where * 14 + i] - '0') << (13 - i);
	}
	return msk;
}

Benjamin

//bs:flags:grader.cpp
#include "Ali.h"
#include "Benjamin.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

namespace x = __gnu_pbds;
template <typename T>
using ordered_set = x::tree<T, x::null_type, less<T>, x::rb_tree_tag, x::tree_order_statistics_node_update>;

template <typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;

#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
#define x first
#define y second
using ll = long long;
using ld = long double;

const int N = 1e4 + 10;

int n;
vector<int> g[N];


int get_forward(int x, int y) {
	return y * (y + 1) / 2 + x;
}

pair<int, int> get_backward(int num) {
	int lef = 0, rig = n;
	while (rig - lef > 1) {
		int mid = (lef + rig) / 2;
		if (mid * (mid + 1) / 2 <= num) {
			lef = mid;
		} else {
			rig = mid;
		}
	}
	return {num - lef * (lef + 1) / 2, lef};
}

int dfs(int u, int w, int p = -1) {
	if (u == w) {
		return 0;
	}
	for (int v : g[u]) {
		if (v != p) {
			int ans = dfs(v, w, u);
			if (ans != -1) {
				return ans + 1;
			}
		}
	}
	return -1;
}

string SendA(string s) {
	int msk = 0;
	for (int i = 0; i < 20; ++i) {
		msk |= (s[i] - '0') << (19 - i);
	}
	ostringstream oss;
	while (msk < get_forward(0, n)) {
		auto [x, y] = get_backward(msk);
		oss << bitset<14>(dfs(x, y));
		msk += (1 << 20);
	}
	return oss.str();
}

int x, y;

string SendB(int n_, int x_, int y_) {
	n = n_, x = x_, y = y_;
	if (x > y) {
		swap(x, y);
	}
	ostringstream oss;
	oss << bitset<20>(get_forward(x, y) % (1 << 20));
	return oss.str();
}

int Answer(string t) {
	int where = get_forward(x, y) / (1 << 20);
	int msk = 0;
	for (int i = 0; i < 14; ++i) {
		msk |= (t[where * 14 + i] - '0') << (13 - i);
	}
	return msk;
}

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