oj.uz

Submission #466028

# Submission time Handle Problem Language Result Execution time Memory
466028 2021-08-17T15:07:39 Z nonsensenonsense1 Monster Game (JOI21_monster) C++17
0 / 100
 121 ms 400 KB 
#include "monster.h"
#include <vector>
#include <cstring>
#include <numeric>

const int N = 1000;
int a[N], aux[N], less[N];

void run(int l, int r) 
{
	if (r - l <= 1) return;
	int m = l + r >> 1;
	run(l, m);
	run(m, r);
	for (int i = 0, j = 0; i + j < r - l;) {
		if (l + i < m && (m + j == r || Query(a[m + j], a[l + i]))) {
			aux[i + j] = a[l + i];
			++i;
		}
		else {
			aux[i + j] = a[m + j];
			++j;
		}
	}
	memcpy(a + l, aux, r - l << 2);
}

std::vector<int> Solve(int n) 
{
	std::iota(a, a + n, 0);
	run(0, n);
	int k = std::min(n, 12);
	for (int i = 0; i < k; ++i) for (int j = i + 1; j < k; ++j) {
		if (Query(a[i], a[j])) ++less[i];
		else ++less[j];
	}
	int z = -1;
	for (int i = 0; i < k; ++i) if (less[i] == 1) if (z == -1 || Query(a[i], a[z])) z = i;
	int prev = 0;
	std::vector<int> ans(n);
	while (prev < n) {
		for (int i = z; i >= prev; --i) ans[a[i]] = prev + z - i;
		int z_ = z;
		if (prev < n) for (++z; !Query(a[prev], a[z]); ++z);
		prev = z_ + 1;
	}
	return ans;
}

Compilation message

monster.cpp: In function 'void run(int, int)':
monster.cpp:12:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 |  int m = l + r >> 1;
      |          ~~^~~
monster.cpp:25:23: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   25 |  memcpy(a + l, aux, r - l << 2);
      |                     ~~^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 200 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 200 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 320 KB Output is correct
2 Correct 40 ms 288 KB Output is correct
3 Correct 97 ms 276 KB Output is correct
4 Correct 119 ms 272 KB Output is correct
5 Correct 121 ms 268 KB Output is correct
6 Incorrect 64 ms 400 KB Wrong Answer [5]
7 Halted 0 ms 0 KB -