oj.uz

Submission #544595

# Submission time Handle Problem Language Result Execution time Memory
544595 2022-04-02T13:16:53 Z pavement Super Dango Maker (JOI22_dango3) C++17
100 / 100
 7980 ms 700 KB 
#include "dango3.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back

namespace {

int N, M;
vector<int> x, vec[26];

void complement() {
	vector<int> nx;
	sort(x.begin(), x.end());
	for (int i = 1; i <= N * M; i++)
		if (!binary_search(x.begin(), x.end(), i)) nx.pb(i);
	x = nx;
}

};

void Solve(int N, int M) {
	::N = N;
	::M = M;
	for (int i = 1; i <= N * M; i++) {
		int lo = 1, hi = M, ans = -1;
		while (lo <= hi) {
			int mid = (lo + hi) / 2;
			x.clear();
			for (int j : vec[mid]) x.pb(j);
			x.pb(i);
			complement();
			if (M - Query(x) == 1) ans = mid, hi = mid - 1;
			else lo = mid + 1;
		}
		vec[ans].pb(i);
	}
	for (int i = 1; i <= M; i++) Answer(vec[i]);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 344 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 59 ms 356 KB Output is correct
2 Correct 63 ms 360 KB Output is correct
3 Correct 55 ms 360 KB Output is correct
4 Correct 55 ms 368 KB Output is correct
5 Correct 50 ms 356 KB Output is correct
6 Correct 51 ms 356 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1834 ms 472 KB Output is correct
2 Correct 1863 ms 464 KB Output is correct
3 Correct 1883 ms 480 KB Output is correct
4 Correct 1954 ms 448 KB Output is correct
5 Correct 1629 ms 452 KB Output is correct
6 Correct 1690 ms 464 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 7980 ms 600 KB Output is correct
2 Correct 7919 ms 700 KB Output is correct
3 Correct 7903 ms 616 KB Output is correct
4 Correct 7888 ms 612 KB Output is correct
5 Correct 6965 ms 684 KB Output is correct
6 Correct 6951 ms 568 KB Output is correct