oj.uz

Submission #905958

# Submission time Handle Problem Language Result Execution time Memory
905958 2024-01-13T07:50:05 Z daoquanglinh2007 Super Dango Maker (JOI22_dango3) C++17
100 / 100
 2134 ms 1136 KB 
#include "dango3.h"

#include <bits/stdc++.h>

using namespace std;

int N, M;
bool mark[10005];

int Ask(vector <int> &v){
	memset(mark, 0, sizeof(mark));
	for (int i : v) mark[i] = 1;
	vector <int> sv(0);
	for (int i = 1; i <= N*M; i++)
		if (!mark[i]) sv.push_back(i);
	return M-Query(sv);
}

void Solve(int a, int b) {
	N = a, M = b;
	vector <int> g[M+1], v;
	for (int i = 1; i <= M; i++) g[i].clear();
	for (int i = 1; i <= N*M; i++){
		int l = 1, r = M, res = -1;
		while (l <= r){
			int mid = (l+r)/2;
			v.clear();
			for (int j = 1; j <= mid; j++)
				for (int x : g[j]) v.push_back(x);
			v.push_back(i);
			if (Ask(v) <= mid){
				res = mid;
				r = mid-1;
			}
			else l = mid+1;
		}
		g[res].push_back(i);
	}
	for (int i = 1; i <= M; i++) Answer(g[i]);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 504 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 516 KB Output is correct
2 Correct 18 ms 344 KB Output is correct
3 Correct 21 ms 344 KB Output is correct
4 Correct 17 ms 348 KB Output is correct
5 Correct 18 ms 344 KB Output is correct
6 Correct 17 ms 348 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 572 KB Output is correct
2 Correct 511 ms 776 KB Output is correct
3 Correct 555 ms 856 KB Output is correct
4 Correct 536 ms 600 KB Output is correct
5 Correct 489 ms 596 KB Output is correct
6 Correct 493 ms 580 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 1988 ms 1136 KB Output is correct
2 Correct 1996 ms 940 KB Output is correct
3 Correct 2128 ms 920 KB Output is correct
4 Correct 2134 ms 696 KB Output is correct
5 Correct 1953 ms 704 KB Output is correct
6 Correct 1959 ms 668 KB Output is correct