Submission #630791

#	Time	Username	Problem	Language	Result	Execution time	Memory
630791		jwvg0425	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	16 ms	1412 KiB

prison

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

vector<int> bits[5005];
int bitMax[25];

void makeBits2(int l, int r)
{
	int lx = l + 1, rx = r - 1;
	int m = (lx + rx) / 2;

	for (int i = l; i <= r; i++)
	{
		if (i == l)
		{
			bits[i].push_back(-1);
			continue;
		}

		if (i == r)
		{
			bits[i].push_back(-2);
			continue;
		}

		if (i <= m)
			bits[i].push_back(0);
		else
			bits[i].push_back(1);
	}

	if (lx <= m)
		makeBits2(lx, m);

	if (m + 1 <= rx)
		makeBits2(m + 1, rx);
}

void makeBits(int l, int r)
{
	if (l > r)
		return;

	if (r - l + 1 <= 64)
	{
		makeBits2(l, r);
		return;
	}

	int lx = l + 1, rx = r - 1;
	int sub = (rx - lx + 2) / 3;

	int m1 = lx + sub;
	int m2 = lx + sub * 2;

	// lx ~ m1, m1 + 1 ~ m2, m2 + 1 ~ rx

	for (int i = l; i <= r; i++)
	{
		if (i == l)
		{
			bits[i].push_back(-1);
			continue;
		}

		if (i == r)
		{
			bits[i].push_back(-2);
			continue;
		}

		if (i <= m1)
			bits[i].push_back(0);
		else if (i <= m2)
			bits[i].push_back(1);
		else
			bits[i].push_back(2);
	}

	if (lx > rx)
		return;

	makeBits(lx, m1);
	makeBits(m1 + 1, m2);
	makeBits(m2 + 1, rx);
}

int maxBit = 0;

void process(vector<vector<int>>& res, int n, int turn, int bit, int st)
{
	if (bit == maxBit)
		return;

	int nxt = st;
	for (int pre = 0; pre < bitMax[bit - 1]; pre++)
	{
		res.push_back(vector<int>(n + 1, 0));
		res.back()[0] = turn;
		nxt++;
	}

	int me = -(turn + 1);
	int other = -((turn + 1) % 2 + 1);

	for (int i = 1; i <= n; i++)
	{
		if (bits[i].size() <= bit - 1)
			continue;

		for (int pre = 0; pre < bitMax[bit - 1]; pre++)
		{
			if (bits[i][bit - 1] == -1)
				res[st + pre][i] = me;
			else if (bits[i][bit - 1] == -2)
				res[st + pre][i] = other;
			else if (bits[i][bit - 1] < pre)
				res[st + pre][i] = me;
			else if (bits[i][bit - 1] > pre)
				res[st + pre][i] = other;
			else
			{
				if (bits[i].size() <= bit)
					continue;

				if (bits[i][bit] == -1)
					res[st + pre][i] = me;
				else if (bits[i][bit] == -2)
					res[st + pre][i] = other;
				else
					res[st + pre][i] = nxt + bits[i][bit];
			}
		}
	}

	process(res, n, (turn + 1) % 2, bit + 1, nxt);
}

vector<vector<int>> devise_strategy(int N)
{
	vector<vector<int>> res;

	makeBits(1, N);

	for (int i = 1; i <= N; i++)
		maxBit = max(maxBit, (int)bits[i].size());

	for (int bit = 0; bit < maxBit; bit++)
	{
		for (int i = 1; i <= N; i++)
		{
			if (bits[i].size() <= bit)
				continue;

			bitMax[bit] = max(bitMax[bit], bits[i][bit] + 1);
		}
	}

	res.push_back(vector<int>(N + 1, 0));

	for (int i = 1; i <= N; i++)
	{
		if (bits[i][0] == -1)
			res[0][i] = -1;
		else if (bits[i][0] == 0)
			res[0][i] = 1;
		else if (bits[i][0] == 1)
			res[0][i] = 2;
		else if (bits[i][0] == 2)
			res[0][i] = 3;
		else
			res[0][i] = -2;
	}

	process(res, N, 1, 1, 1);

	return res;
}

Compilation message (stderr)

prison.cpp: In function 'void process(std::vector<std::vector<int> >&, int, int, int, int)':
prison.cpp:133:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  133 |   if (bits[i].size() <= bit - 1)
      |       ~~~~~~~~~~~~~~~^~~~~~~~~~
prison.cpp:148:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  148 |     if (bits[i].size() <= bit)
      |         ~~~~~~~~~~~~~~~^~~~~~
prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:177:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  177 |    if (bits[i].size() <= bit)
      |        ~~~~~~~~~~~~~~~^~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 90 / 90