Submission #547417

#	Time	Username	Problem	Language	Result	Execution time	Memory
547417		skittles1412	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	1615 ms	644 KiB

dango3

#include "dango3.h"
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

const long mod = 1e9 + 7;

long hsh(const vector<int> &arr, long base) {
	long ans = 0;
	for (auto& a : arr) {
		ans = (ans * base + a + 1) % mod;
	}
	return ans;
}

struct chash {
	uint64_t operator()(vector<int> arr) const {
		sort(begin(arr), end(arr));
		uint64_t ans = hsh(arr, int(1e4) + 5);
		ans <<= 32;
		ans |= hsh(arr, int(1e4) + 7);
		ans ^= ans << 5;
		ans ^= ans >> 11;
		ans ^= ans >> 7;
		return ans;
	}
};

int query(vector<int> arr) {
	for (auto& a : arr) {
		a++;
	}
	return Query(arr);
}

void answer(vector<int> arr) {
	for (auto& a : arr) {
		a++;
	}
	Answer(arr);
}

vector<int> concat(vector<int> a, const vector<int> &b) {
	a.insert(a.end(), begin(b), end(b));
	return a;
}

void Solve(int n, int m) {
	static mt19937 cowng(chrono::steady_clock::now().time_since_epoch().count());
	int cnts[m + 1] {};
	bool vis[n * m] {};
	for (int i = m; i >= 1; i--) {
		vector<int> cur;
		for (int j = 0; j < n * m; j++) {
			if (!vis[j]) {
				cur.push_back(j);
			}
		}
		int cmn = query(cur);
		while (sz(cur) > 3 * n) {
			cnts[sz(cur) / n]++;
			shuffle(begin(cur), end(cur), cowng);
			vector<int> ncur(cur.begin(), cur.begin() + sz(cur) - max(5, cmn));
			int nmn = query(ncur);
			if (nmn >= 1) {
				cur = ncur;
				cmn = nmn;
			}
		}
		while (sz(cur) > n) {
			cnts[sz(cur) / n]++;
			vector<int> ncur(cur.begin(), cur.end() - 1);
			if (query(ncur) >= 1) {
				cur.pop_back();
			} else {
				cur.insert(cur.begin(), cur.back());
				cur.pop_back();
			}
		}
		answer(cur);
		for (auto& a : cur) {
			vis[a] = true;
		}
	}
	for (int i = 1; i <= m; i++) {
		dbg(i, cnts[i]);
	}
}

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 78 / 78