oj.uz

Submission #675699

# Submission time Handle Problem Language Result Execution time Memory
675699 2022-12-27T18:09:31 Z vovamr Super Dango Maker (JOI22_dango3) C++17
100 / 100
 4351 ms 1444 KB 
#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

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;
      |           ~~^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 0 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 1 ms 340 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 340 KB Output is correct
2 Correct 29 ms 384 KB Output is correct
3 Correct 29 ms 392 KB Output is correct
4 Correct 27 ms 340 KB Output is correct
5 Correct 29 ms 340 KB Output is correct
6 Correct 26 ms 384 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 980 ms 576 KB Output is correct
2 Correct 973 ms 600 KB Output is correct
3 Correct 979 ms 600 KB Output is correct
4 Correct 969 ms 656 KB Output is correct
5 Correct 889 ms 600 KB Output is correct
6 Correct 954 ms 764 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 4319 ms 824 KB Output is correct
2 Correct 4351 ms 828 KB Output is correct
3 Correct 4157 ms 1324 KB Output is correct
4 Correct 4255 ms 1444 KB Output is correct
5 Correct 4121 ms 852 KB Output is correct
6 Correct 4197 ms 1112 KB Output is correct