# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
675693 | vovamr | Super Dango Maker (JOI22_dango3) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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);
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 = 0; 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);
else return rec(md + 1, r, ID);
}
void Solve(int n, int m) {
answer.resize(m);
for (int id = 0; 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]);
}
}