oj.uz

Submission #617437

# Submission time Handle Problem Language Result Execution time Memory
617437 2022-08-01T11:20:24 Z patrikpavic2 Super Dango Maker (JOI22_dango3) C++17
100 / 100
 722 ms 764 KB 
#include "dango3.h"
#include <vector>
#include <algorithm>
#include <cstdio>

#define PB push_back

using namespace std;

typedef vector < int > vi;

namespace {

const int MAXN = 1e6 + 500;

int sve[MAXN];

void divnconq(vi v, vi sig, int k){
	if(k == 1){ 
		for(int &x : sig) v.PB(x);
		Answer(v); return; 
	}
	int c = k / 2, n = (int)(v.size() + sig.size()) / k;
	vi kog = sig, ost;
	int ret = 0;
	for(int j = 16;j >= 0;j--){
		if(ret + (1 << j) < (int)v.size()){
			for(int k = 0;k < (1 << j);k++) kog.PB(v[ret + k]);
			if(Query(kog) >= c)
				for(int k = 0;k < (1 << j);k++) kog.pop_back();
			else
				ret += (1 << j);
		}
	}
	kog.PB(v[ret]);
	for(int &x : v) sve[x] = 1;
	for(int &x : kog) sve[x] = 0;
	for(int &x : v)
		if(sve[x]) ost.PB(x);
	vi vis;
	while((int)kog.size() > c * n){
		int st = kog.back();
		kog.pop_back();
		if(Query(kog) < c)
			kog.insert(kog.begin(), st);
		else
			vis.PB(st);
	}
	divnconq(kog, {}, c);
	divnconq(ost, vis, k - c);
}

}

void Solve(int n, int m) {
	vi poc;
	for(int i = 1;i <= n * m;i++)
		poc.PB(i);
	divnconq(poc, {}, m);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 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 340 KB Output is correct
5 Correct 1 ms 292 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 4 ms 340 KB Output is correct
2 Correct 6 ms 340 KB Output is correct
3 Correct 9 ms 340 KB Output is correct
4 Correct 8 ms 376 KB Output is correct
5 Correct 2 ms 296 KB Output is correct
6 Correct 2 ms 340 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 532 KB Output is correct
2 Correct 113 ms 468 KB Output is correct
3 Correct 181 ms 656 KB Output is correct
4 Correct 187 ms 556 KB Output is correct
5 Correct 19 ms 468 KB Output is correct
6 Correct 13 ms 564 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 748 KB Output is correct
2 Correct 258 ms 764 KB Output is correct
3 Correct 590 ms 752 KB Output is correct
4 Correct 722 ms 756 KB Output is correct
5 Correct 77 ms 720 KB Output is correct
6 Correct 60 ms 736 KB Output is correct