Submission #1283396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283396		am_aadvik	Monster Game (JOI21_monster)	C++20	89 / 100	32 ms	444 KiB

monster

#define SUBMIT 1
#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include<iostream>
#include <algorithm>
#include<map>
#include<set>
using namespace std;
#ifdef SUBMIT
#include "monster.h"
#else

#include <cstdio>
#include <cstdlib>
namespace {
	using std::exit;
	using std::fprintf;
	using std::printf;
	using std::scanf;
	constexpr int Q_MAX = 25'000;
	constexpr int N_MAX = 1'000;
	int N;
	int S[N_MAX];
	int query_count = 0;
	void WrongAnswer(int code) {
		printf("Wrong Answer [%d]\n", code);
		exit(0);
	}
}
bool Query(int a, int b) {
	if (++query_count > Q_MAX) WrongAnswer(6);
	if (a < 0 || N <= a || b < 0 || N <= b) WrongAnswer(4);
	if (a == b) WrongAnswer(5);
	return (S[a] > S[b]) ^ (abs(S[a] - S[b]) == 1);
}
vector<int> Solve(int n);
int main() {
	if (scanf("%d", &N) != 1) {
		fprintf(stderr, "Error while reading.\n");
		exit(1);
	}
	for (int i = 0; i < N; i++) {
		if (scanf("%d", S + i) != 1) {
			fprintf(stderr, "Error while reading.\n");
			exit(1);
		}
	}
	for (int t = 0; t < 20; ++t) {
		std::vector<int> T = Solve(N);
		if ((int)T.size() != N) WrongAnswer(1);
		for (int i = 0; i < N; i++) {
			if (T[i] < 0 || N <= T[i]) WrongAnswer(2);
			if (T[i] != S[i]) WrongAnswer(3);
		}
		printf("Accepted: %d\n", query_count);
		query_count = 0;
	}
	return 0;
}
#endif

//main code
#include <random> 

bool q(int a, int b) { return Query(a, b); }
vector<int> msort(vector<int> &a) {
	if (a.size() <= 1) return a;
	vector<int> l, r, sa;
	int n = a.size();
	for (int i = 0; i < (n / 2); ++i)
		l.push_back(a[i]);
	for (int i = n / 2; i < n; ++i)
		r.push_back(a[i]);
	l = msort(l), r = msort(r);
	int pl = 0, pr = 0;
	while ((pl < l.size()) || (pr < r.size())) {
		if (pl == l.size()) sa.push_back(r[pr]), pr++;
		else if (pr == r.size()) sa.push_back(l[pl]), pl++;
		else if(q(l[pl], r[pr])) sa.push_back(r[pr]), pr++;
		else sa.push_back(l[pl]), pl++;
	}
	return sa;
}
int find0(int n, vector<int> l) {
	int m = l.size();
	vector<int> win(n);
	for (auto x : l)
		for (int y : l)
			if (x != y)
				if (q(x, y)) ++win[x];
				else ++win[y];
	for (auto& x : win) x /= 2;
	vector<int> w1, wn;
	for(int i = 0; i < l.size(); ++i)
		if (win[l[i]] == 1) 
			w1.push_back(i);
	auto r1 = q(l[w1[0]], l[w1[1]]);
	if (r1) return w1[0];
	else return w1[1];
}
void rev(int i, int j, vector<int>& a) {
	while (i < j) swap(a[i], a[j]), i++, j--;
}
vector<int> Solve(int n) {
	vector<int> a(n);
	for (int i = 0; i < n; a[i] = i, ++i);
	a = msort(a);
	vector<int> f(min(50, n));
	for (int i = 0; i < min(50, n); ++i) f[i] = a[i];
	int p = find0(n, f);
	for (int i = p - 1; i >= 0; --i) swap(a[i + 1], a[i]);
	p = 0;
	while (1) {
		int j = -1;
		for(int i = p + 1; i < n; ++i)
			if (q(a[p], a[i])) { j = i; break; }
		if (j == -1) break;
		rev(p + 1, j, a);
		p = j;
	}
	vector<int> res(n);
	for (int i = 0; i < n; ++i)
		res[a[i]] = i;
	return res;
}

Compilation message (stderr)

In file included from /usr/include/c++/13/vector:62,
                 from monster.cpp:3:
In static member function 'static constexpr _Up* std::__copy_move<_IsMove, true, std::random_access_iterator_tag>::__copy_m(_Tp*, _Tp*, _Up*) [with _Tp = const int; _Up = int; bool _IsMove = false]',
    inlined from 'constexpr _OI std::__copy_move_a2(_II, _II, _OI) [with bool _IsMove = false; _II = const int*; _OI = int*]' at /usr/include/c++/13/bits/stl_algobase.h:506:30,
    inlined from 'constexpr _OI std::__copy_move_a1(_II, _II, _OI) [with bool _IsMove = false; _II = const int*; _OI = int*]' at /usr/include/c++/13/bits/stl_algobase.h:533:42,
    inlined from 'constexpr _OI std::__copy_move_a(_II, _II, _OI) [with bool _IsMove = false; _II = __gnu_cxx::__normal_iterator<const int*, vector<int> >; _OI = int*]' at /usr/include/c++/13/bits/stl_algobase.h:540:31,
    inlined from 'constexpr _OI std::copy(_II, _II, _OI) [with _II = __gnu_cxx::__normal_iterator<const int*, vector<int> >; _OI = int*]' at /usr/include/c++/13/bits/stl_algobase.h:633:7,
    inlined from 'static _ForwardIterator std::__uninitialized_copy<true>::__uninit_copy(_InputIterator, _InputIterator, _ForwardIterator) [with _InputIterator = __gnu_cxx::__normal_iterator<const int*, std::vector<int> >; _ForwardIterator = int*]' at /usr/include/c++/13/bits/stl_uninitialized.h:147:27,
    inlined from '_ForwardIterator std::uninitialized_copy(_InputIterator, _InputIterator, _ForwardIterator) [with _InputIterator = __gnu_cxx::__normal_iterator<const int*, vector<int> >; _ForwardIterator = int*]' at /usr/include/c++/13/bits/stl_uninitialized.h:185:15,
    inlined from 'constexpr _ForwardIterator std::__uninitialized_copy_a(_InputIterator, _InputIterator, _ForwardIterator, allocator<_Tp>&) [with _InputIterator = __gnu_cxx::__normal_iterator<const int*, vector<int> >; _ForwardIterator = int*; _Tp = int]' at /usr/include/c++/13/bits/stl_uninitialized.h:373:37,
    inlined from 'constexpr std::vector<_Tp, _Alloc>::vector(const std::vector<_Tp, _Alloc>&) [with _Tp = int; _Alloc = std::allocator<int>]' at /usr/include/c++/13/bits/stl_vector.h:606:31,
    inlined from 'std::vector<int> msort(std::vector<int>&)' at monster.cpp:67:28:
/usr/include/c++/13/bits/stl_algobase.h:437:30: warning: 'void* __builtin_memmove(void*, const void*, long unsigned int)' writing between 5 and 9223372036854775807 bytes into a region of size 4 overflows the destination [-Wstringop-overflow=]
  437 |             __builtin_memmove(__result, __first, sizeof(_Tp) * _Num);
      |             ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/c++allocator.h:33,
                 from /usr/include/c++/13/bits/allocator.h:46,
                 from /usr/include/c++/13/vector:63:
In member function '_Tp* std::__new_allocator<_Tp>::allocate(size_type, const void*) [with _Tp = int]',
    inlined from 'constexpr _Tp* std::allocator< <template-parameter-1-1> >::allocate(std::size_t) [with _Tp = int]' at /usr/include/c++/13/bits/allocator.h:198:40,
    inlined from 'static constexpr _Tp* std::allocator_traits<std::allocator<_Up> >::allocate(allocator_type&, size_type) [with _Tp = int]' at /usr/include/c++/13/bits/alloc_traits.h:482:28,
    inlined from 'constexpr std::_Vector_base<_Tp, _Alloc>::pointer std::_Vector_base<_Tp, _Alloc>::_M_allocate(std::size_t) [with _Tp = int; _Alloc = std::allocator<int>]' at /usr/include/c++/13/bits/stl_vector.h:381:33,
    inlined from 'constexpr std::_Vector_base<_Tp, _Alloc>::pointer std::_Vector_base<_Tp, _Alloc>::_M_allocate(std::size_t) [with _Tp = int; _Alloc = std::allocator<int>]' at /usr/include/c++/13/bits/stl_vector.h:378:7,
    inlined from 'constexpr void std::_Vector_base<_Tp, _Alloc>::_M_create_storage(std::size_t) [with _Tp = int; _Alloc = std::allocator<int>]' at /usr/include/c++/13/bits/stl_vector.h:398:44,
    inlined from 'constexpr std::_Vector_base<_Tp, _Alloc>::_Vector_base(std::size_t, const allocator_type&) [with _Tp = int; _Alloc = std::allocator<int>]' at /usr/include/c++/13/bits/stl_vector.h:335:26,
    inlined from 'constexpr std::vector<_Tp, _Alloc>::vector(const std::vector<_Tp, _Alloc>&) [with _Tp = int; _Alloc = std::allocator<int>]' at /usr/include/c++/13/bits/stl_vector.h:603:61,
    inlined from 'std::vector<int> msort(std::vector<int>&)' at monster.cpp:67:28:
/usr/include/c++/13/bits/new_allocator.h:151:55: note: destination object of size 4 allocated by 'operator new'
  151 |         return static_cast<_Tp*>(_GLIBCXX_OPERATOR_NEW(__n * sizeof(_Tp)));
      |                                                       ^

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 64 / 75