oj.uz

Submission #547417

# Submission time Handle Problem Language Result Execution time Memory
547417 2022-04-10T16:13:49 Z skittles1412 Super Dango Maker (JOI22_dango3) C++17
100 / 100
 1615 ms 644 KB 
#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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 340 KB Output is correct
2 Correct 10 ms 420 KB Output is correct
3 Correct 11 ms 436 KB Output is correct
4 Correct 10 ms 428 KB Output is correct
5 Correct 11 ms 340 KB Output is correct
6 Correct 11 ms 376 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 472 KB Output is correct
2 Correct 377 ms 464 KB Output is correct
3 Correct 367 ms 460 KB Output is correct
4 Correct 370 ms 460 KB Output is correct
5 Correct 370 ms 468 KB Output is correct
6 Correct 354 ms 472 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 1576 ms 536 KB Output is correct
2 Correct 1578 ms 536 KB Output is correct
3 Correct 1615 ms 532 KB Output is correct
4 Correct 1591 ms 644 KB Output is correct
5 Correct 1585 ms 536 KB Output is correct
6 Correct 1604 ms 536 KB Output is correct