Submission #675699

#TimeUsernameProblemLanguageResultExecution timeMemory
675699vovamrSuper Dango Maker (JOI22_dango3)C++17
100 / 100
4351 ms1444 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "dango3.h"
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }
 
ve<ve<int>> answer;
 
inline int rec(int l, int r, int ID, const int &n, const int &m) {
	if (l == r) return l;
 
	int md = l + r >> 1;
 
	ve<bool> have(n * m + 1);
	have[ID] = 1;
 
	for (int i = l; i <= md; ++i) {
		for (auto &x : answer[i]) {
			have[x] = 1;
		}
	}
 
	ve<int> to_ask;
	for (int i = 1; i <= n * m; ++i) {
		if (have[i]) continue;
		to_ask.pb(i);
	}
 
	int res = Query(to_ask);
	int left = m - 1 - (md - l + 1);
 
	if (res != left) return rec(l, md, ID, n, m);
	else return rec(md + 1, r, ID, n, m);
}
 
void Solve(int n, int m) {
	answer.resize(m);
	for (int id = 1; id <= n * m; ++id) {
		int go = rec(0, m - 1, id, n, m);
		answer[go].pb(id);
	}
	for (int i = 0; i < m; ++i) {
		Answer(answer[i]);
	}
}

Compilation message (stderr)

dango3.cpp: In function 'int rec(int, int, int, const int&, const int&)':
dango3.cpp:29:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |  int md = l + r >> 1;
      |           ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...