oj.uz

Submission #905955

# Submission time Handle Problem Language Result Execution time Memory
905955 2024-01-13T07:48:45 Z daoquanglinh2007 Super Dango Maker (JOI22_dango3) C++17
100 / 100
 6697 ms 920 KB 
#include "dango3.h"

#include <bits/stdc++.h>

using namespace std;

int N, M;

int Ask(vector <int> &v){
	sort(v.begin(), v.end());
	vector <int> sv(0);
	int j = 1;
	for (int i : v){
		while (j < i) sv.push_back(j++);
		j++;
	}
	while (j <= N*M) sv.push_back(j++);
	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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 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 39 ms 348 KB Output is correct
2 Correct 38 ms 348 KB Output is correct
3 Correct 34 ms 348 KB Output is correct
4 Correct 30 ms 348 KB Output is correct
5 Correct 21 ms 500 KB Output is correct
6 Correct 22 ms 348 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1691 ms 584 KB Output is correct
2 Correct 1712 ms 584 KB Output is correct
3 Correct 1242 ms 840 KB Output is correct
4 Correct 1261 ms 604 KB Output is correct
5 Correct 1078 ms 564 KB Output is correct
6 Correct 1010 ms 572 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 6697 ms 676 KB Output is correct
2 Correct 6591 ms 696 KB Output is correct
3 Correct 5066 ms 920 KB Output is correct
4 Correct 5023 ms 744 KB Output is correct
5 Correct 4360 ms 652 KB Output is correct
6 Correct 4051 ms 688 KB Output is correct