oj.uz

Submission #558039

# Submission time Handle Problem Language Result Execution time Memory
558039 2022-05-06T14:21:53 Z DanShaders Flights (JOI22_flights) C++17
32 / 100
 578 ms 1916 KB 
//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;
}

//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

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 912 KB Output is correct
2 Correct 1 ms 912 KB Output is correct
3 Correct 2 ms 912 KB Output is correct
4 Correct 2 ms 912 KB Output is correct
5 Correct 2 ms 912 KB Output is correct
6 Correct 9 ms 1500 KB Output is correct
7 Correct 12 ms 1424 KB Output is correct
8 Correct 11 ms 1424 KB Output is correct
9 Correct 12 ms 1492 KB Output is correct
10 Correct 20 ms 1604 KB Output is correct
11 Correct 7 ms 1368 KB Output is correct
12 Correct 7 ms 1424 KB Output is correct
13 Correct 9 ms 1492 KB Output is correct
14 Correct 9 ms 1496 KB Output is correct
15 Correct 9 ms 1700 KB Output is correct
16 Correct 8 ms 1488 KB Output is correct

Subtask #2
17.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 912 KB Output is correct
2 Partially correct 86 ms 1780 KB Output is partially correct
3 Correct 3 ms 1124 KB Output is correct
4 Partially correct 544 ms 1684 KB Output is partially correct
5 Partially correct 529 ms 1628 KB Output is partially correct
6 Partially correct 562 ms 1688 KB Output is partially correct
7 Partially correct 578 ms 1856 KB Output is partially correct
8 Partially correct 561 ms 1660 KB Output is partially correct
9 Partially correct 323 ms 1828 KB Output is partially correct
10 Partially correct 363 ms 1876 KB Output is partially correct
11 Partially correct 473 ms 1640 KB Output is partially correct
12 Partially correct 32 ms 1476 KB Output is partially correct
13 Partially correct 177 ms 1660 KB Output is partially correct
14 Partially correct 194 ms 1588 KB Output is partially correct
15 Correct 5 ms 912 KB Output is correct
16 Partially correct 375 ms 1916 KB Output is partially correct
17 Partially correct 360 ms 1832 KB Output is partially correct
18 Partially correct 354 ms 1772 KB Output is partially correct
19 Partially correct 398 ms 1904 KB Output is partially correct
20 Partially correct 219 ms 1644 KB Output is partially correct
21 Partially correct 302 ms 1852 KB Output is partially correct
22 Partially correct 325 ms 1616 KB Output is partially correct
23 Partially correct 302 ms 1584 KB Output is partially correct
24 Partially correct 347 ms 1552 KB Output is partially correct
25 Partially correct 323 ms 1620 KB Output is partially correct
26 Partially correct 364 ms 1648 KB Output is partially correct
27 Partially correct 325 ms 1524 KB Output is partially correct
28 Partially correct 341 ms 1728 KB Output is partially correct
29 Partially correct 307 ms 1608 KB Output is partially correct
30 Partially correct 336 ms 1648 KB Output is partially correct
31 Partially correct 311 ms 1668 KB Output is partially correct
32 Partially correct 339 ms 1644 KB Output is partially correct
33 Partially correct 322 ms 1724 KB Output is partially correct
34 Partially correct 336 ms 1560 KB Output is partially correct
35 Partially correct 323 ms 1672 KB Output is partially correct
36 Partially correct 327 ms 1580 KB Output is partially correct
37 Partially correct 288 ms 1664 KB Output is partially correct
38 Partially correct 280 ms 1584 KB Output is partially correct
39 Partially correct 45 ms 1496 KB Output is partially correct
40 Partially correct 540 ms 1904 KB Output is partially correct