Submission #799936

#	Time	Username	Problem	Language	Result	Execution time	Memory
799936		LIF	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	12 ms	2132 KiB

prison

#include "prison.h"
#include<bits/stdc++.h>
#include <vector>
using namespace std;
int s[27][5001];
vector<int> v[5005];
std::vector<std::vector<int> > devise_strategy(int N) {
	int flag = 0;
	s[0][0] = 0;
	for(int i=1;i<=25;i+=2)
	{
		if(flag % 2 == 0)
		{
			s[i][0] = 1;
			s[i+1][0] = 1;
		}
		else
		{
			s[i][0] = 0;
			s[i+1][0] = 0;
		}
		flag++;
	}

	for(int i=1;i<=5000;i++)
	{
		int num = i;
		while(num > 0)
		{
			if(num % 2 == 1)v[i].push_back(1);
			else v[i].push_back(0);
			num /= 2;
		}
		for(int j=1;j<=20;j++)if(v[i].size() < 13)v[i].push_back(0);
		reverse(v[i].begin(),v[i].end());
	}
	//0:
	for(int i=1;i<=5000;i++)
	{
		if(v[i][0] == 1)s[0][i] = 1;
		else s[0][i] = 2;
	}
	
	//1 to 23;
	flag = 0;
	int pos = 0;
	for(int i=1;i<=21;i+=2)
	{
		if(flag %2  == 0) // we check b;
		{
			for(int j=1;j<=5000;j++)if(v[j][pos] == 0)s[i][j] = -2;
			for(int j=1;j<=5000;j++)if(v[j][pos] == 1)s[i+1][j] = -1; 
		}
		else
		{
			for(int j=1;j<=5000;j++)if(v[j][pos] == 0)s[i][j] = -1;
			for(int j=1;j<=5000;j++)if(v[j][pos] == 1)s[i+1][j] = -2; 
		}
		for(int j=1;j<=5000;j++)
		{
			if(s[i][j] == -1 || s[i][j] == -2)continue;
			//check pos+1;
			if(v[j][pos+1] == 1)s[i][j] = i+2;
			else s[i][j] = i+3;
		}
		for(int j=1;j<=5000;j++)
		{
			if(s[i+1][j] == -1 || s[i+1][j] == -2)continue;
			//check pos+1;
			if(v[j][pos+1] == 1)s[i+1][j] = i+2;
			else s[i+1][j] = i+3;
		}
		flag++;
		pos++;
	}
	//23:
	for(int i=1;i<=5000;i++)
	{
		if(v[i][11] == 0)s[23][i] = -1;
		else
		{
			if(v[i][12] == 1)s[23][i] = -2;
			else s[23][i] = -1;
		}
	}
	//24:
	for(int i=1;i<=5000;i++)
	{
		if(v[i][11] == 1)s[24][i] = -2;
		else
		{
			if(v[i][12] == 1)s[24][i] = -2;
			else s[24][i] = -1;
		}
	}
	/*for(int i=22;i<=23;i++)
	{
		for(int j=1;j<=5000;j++)
		{
			cout<<i<<" "<<j<<" "<<s[i][j]<<endl;
		}
	}*/

	/*
	//25:CHECK B
	
	for(int j=1;j<=5000;j++)
	{
		s[25][j] = -2;
	}
	
	//26:
	for(int j=1;j<=5000;j++)
	{
		s[26][j] = -1;
	}
	*/
	vector< vector<int> > ans;
	for(int i=0;i<=24;i++)
	{
		vector<int> temp;
		for(int j=0;j<=N;j++)temp.push_back(s[i][j]);
		ans.push_back(temp);
	}
	return ans;
  
}

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