oj.uz

Submission #714469

# Submission time Handle Problem Language Result Execution time Memory
714469 2023-03-24T15:13:54 Z hollwo_pelw Super Dango Maker (JOI22_dango3) C++17
100 / 100
 1564 ms 1016 KB 
#include "dango3.h"

#include <bits/stdc++.h>
using namespace std;

namespace {

int n, m, f[100000];

}  // namespace

inline vector<int> exclude(vector<int> a, vector<int> b) {
	vector<int> res;
	for (int x : b) f[x] = 1;
	for (int x : a) if (!f[x])
		res.push_back(x);
	for (int x : b) f[x] = 0;
	return res;
}

void solve(vector<int> ids) {
	int sz = ids.size() / n, new_sz = sz / 2;
	// cout << "DIVIDE " << ids.size() << '\n';
	// for (int i : ids) { cout << i << ' '; } cout << '\n';
	if (sz == 1)
		return Answer(ids);
	vector<int> oth;
	for (int x : ids) {
		oth.push_back(x);
		if (Query(exclude(ids, oth)) < new_sz)
			oth.pop_back();
	}
	solve(exclude(ids, oth)), solve(oth);
}

void Solve(int N, int M) {
	n = N, m = M;
	vector<int> ids(n * m);
	iota(ids.begin(), ids.end(), 1);
	solve(ids);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 304 KB Output is correct
5 Correct 1 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 17 ms 432 KB Output is correct
2 Correct 18 ms 384 KB Output is correct
3 Correct 17 ms 340 KB Output is correct
4 Correct 17 ms 412 KB Output is correct
5 Correct 16 ms 432 KB Output is correct
6 Correct 17 ms 436 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 756 KB Output is correct
2 Correct 388 ms 556 KB Output is correct
3 Correct 400 ms 608 KB Output is correct
4 Correct 395 ms 720 KB Output is correct
5 Correct 405 ms 680 KB Output is correct
6 Correct 383 ms 732 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 1530 ms 844 KB Output is correct
2 Correct 1504 ms 864 KB Output is correct
3 Correct 1562 ms 968 KB Output is correct
4 Correct 1564 ms 1016 KB Output is correct
5 Correct 1520 ms 980 KB Output is correct
6 Correct 1525 ms 820 KB Output is correct