Submission #630758

#	Time	Username	Problem	Language	Result	Execution time	Memory
630758		jwvg0425	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	13 ms	1520 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];

void makeBits(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)
		makeBits(lx, m);

	if (m + 1 <= rx)
		makeBits(m + 1, rx);
}
int maxBit = 0;

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

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

	res[bit * 2 - 1][0] = res[bit * 2][0] = turn;

	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 < 2; pre++)
		{
			if (bits[i][bit - 1] == -1)
				res[bit * 2 - 1 + pre][i] = me;
			else if (bits[i][bit - 1] == -2)
				res[bit * 2 - 1 + pre][i] = other;
			else if (bits[i][bit - 1] < pre)
				res[bit * 2 - 1 + pre][i] = me;
			else if (bits[i][bit - 1] > pre)
				res[bit * 2 - 1 + pre][i] = other;
			else
			{
				if (bits[i].size() <= bit)
					continue;

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

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

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());

	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
			res[0][i] = -2;
	}

	process(res, N, 1, 1);

	return res;
}

Compilation message (stderr)

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

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