oj.uz

Submission #815558

# Submission time Handle Problem Language Result Execution time Memory
815558 2023-08-08T16:55:50 Z Sohsoh84 Super Dango Maker (JOI22_dango3) C++17
100 / 100
 181 ms 564 KB 
#include "dango3.h"
#include <bits/stdc++.h>

using namespace std;

#define all(x)		(x).begin(), (x).end()
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

namespace {
	int variable_example = 1;

}  // namespace

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void Solve(int N, int M) {
	vector<int> vec;
	for (int i = 1; i <= N * M; i++) vec.push_back(i);

	while (int(vec.size()) > N) {
		shuffle(all(vec), rng);
		
		int l = 0, r = int(vec.size()) - 1;
		while (l < r) {
			int mid = (l + r) >> 1;
			vector<int> tmp;
			for (int j = 0; j < mid; j++) tmp.push_back(vec[j]);
			if (Query(tmp)) r = mid;
			else l = mid + 1;
		}

		vector<int> fixed;
		for (int i = 0; i <= l; i++) {
			vector<int> tmp = fixed;
			for (int j = i + 1; j <= l; j++) tmp.push_back(vec[j]);
			if (!Query(tmp)) fixed.push_back(vec[i]);
		}

		for (int e : fixed)
			vec.erase(find(all(vec), e));

		Answer(fixed);
	}

	Answer(vec);
}

Compilation message

dango3.cpp:11:6: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
   11 |  int variable_example = 1;
      |      ^~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 468 KB Output is correct
2 Correct 34 ms 468 KB Output is correct
3 Correct 50 ms 468 KB Output is correct
4 Correct 42 ms 452 KB Output is correct
5 Correct 41 ms 460 KB Output is correct
6 Correct 38 ms 464 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 560 KB Output is correct
2 Correct 151 ms 564 KB Output is correct
3 Correct 169 ms 468 KB Output is correct
4 Correct 162 ms 564 KB Output is correct
5 Correct 168 ms 560 KB Output is correct
6 Correct 175 ms 564 KB Output is correct