Language: C++

// SleepingCats.cpp : ??????????????? ??¢????????±????????§????????¨????????? ?????????????????????????????????
//
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifdef _MSC_VER
#include <intrin.h>
#endif

typedef	struct _cat_inf{
	char	cat_id;
	char	length;
	char	pos;
	char	dummy;
} CAT_INF;

typedef	struct _wall_inf {
	CAT_INF	cat_inf[100];
	unsigned int wall_map[4];
} WALL_INF;

#define	DATFILE "input.txt"
#define	MAXBUF	4096
#define	MAXBITCNT	32
#define	SHIFTBITCNT	5
#define	BITMASK	(0xFFFFFFFF)
static	int count_bits(unsigned);
static	int local_ntz(unsigned);
static	int	local_nlz(unsigned);
static	int	ffstr(unsigned, int);
static	int	judge_sleep(int, int, int, int, WALL_INF *);

int _tmain(int argc, _TCHAR* argv[])
{
	FILE	*fp = NULL;
	char	Buf[MAXBUF];
	char	*tok = NULL;
	char	*next_tok = NULL;
	int		ic;
	int		w_width, cat_width, lines, cat_id;
	char	*err_str;
	int		stat = 0;

	WALL_INF wall_inf;

	fopen_s(&fp,(char *)DATFILE, (char *)"r");

	while (fgets(Buf, MAXBUF, fp) != NULL){
		tok = strtok_s(Buf, " ,	", &next_tok);
		w_width = strtol(tok, &err_str, 10);
		tok = strtok_s(NULL, " ,	", &next_tok);
		lines = strtol(tok, &err_str, 10);
		if (w_width == 0 && lines == 0){
			break;
		}
		memset(wall_inf.wall_map, 0xFF, sizeof(wall_inf.wall_map)); // ????????¢
		memset(wall_inf.cat_inf, 0xFF, sizeof(wall_inf.cat_inf)); // ????????¢
		for (ic = 0; ic < lines; ic++){
			(void)fgets(Buf, MAXBUF, fp);
			tok = strtok_s(Buf, " ,	", &next_tok);
			switch (*tok){
			case	'S':
			case	's':
				tok = strtok_s(NULL, " ,	", &next_tok);
				cat_id = strtol(tok, &err_str, 10);
				tok = strtok_s(NULL, " ,	", &next_tok);
				cat_width = strtol(tok, &err_str, 10);
				stat = judge_sleep(0, cat_id, cat_width, w_width, &wall_inf);
				if (stat == -1){
					fprintf(stdout, "impossible!\n");
				}
				else{
					fprintf(stdout, "%d\n", stat);
				}
				break;
			case	'W':
			case	'w':
				tok = strtok_s(NULL, " ,	", &next_tok);
				cat_id = strtol(tok, &err_str, 10);
				stat = judge_sleep(1, cat_id, -1, w_width, &wall_inf);
				if (stat != 0){
					// error!
					goto pgend;
				}
				break;
			}
		}
		fprintf(stdout, "END\n");
	}
pgend:
	if (fp != NULL){
		fclose(fp);
	}
	return 0;
}

int	judge_sleep(int opr,int cat_id,int cat_width, int w_width, WALL_INF *wall_infP)
{
	unsigned int	umask;
	unsigned int	rsb, lsb, rmsk, lmsk;
	int		ic,jc;
	int		first_ary, last_ary,r;
	int		set_bits;
	int		ret = -1;

	first_ary = last_ary = r = -1;
	lsb = rsb = lmsk = rmsk = 0;
	switch (opr){
	case	0:
		set_bits = cat_width;
		if (wall_infP->cat_inf[cat_id].cat_id != -1){
			goto pgend;
		}
		for (ic = 0; ic < sizeof(wall_infP->wall_map) / sizeof(unsigned int); ic++){
			if (set_bits < MAXBITCNT){
				r = ffstr(wall_infP->wall_map[ic],set_bits);
				if (r < MAXBITCNT){
					umask = (BITMASK) >> (MAXBITCNT - set_bits);
					umask = umask << (MAXBITCNT - set_bits - r);
					if (cat_width + ((ic*MAXBITCNT) + r) <= w_width){
						wall_infP->wall_map[ic] ^= (umask);
						wall_infP->cat_inf[cat_id].cat_id = cat_id;
						wall_infP->cat_inf[cat_id].length = cat_width;
						wall_infP->cat_inf[cat_id].pos = (ic*MAXBITCNT) + r;
						break;
					}
					else{
						goto pgend;
					}
				}
				else{
					rsb = local_ntz(~(wall_infP->wall_map[ic]));
					if (rsb == 0){
						/* ?????????????????\??????????????? */
						continue;
					}
					lsb = local_nlz(~(wall_infP->wall_map[ic+1]));

					if ((rsb + lsb) >= set_bits){
						lsb = set_bits - rsb;
						lmsk = BITMASK >> (MAXBITCNT - rsb);
						rmsk = BITMASK << (MAXBITCNT - lsb);
						if (cat_width + ((ic*MAXBITCNT) + (MAXBITCNT - rsb)) <= w_width){
							wall_infP->wall_map[ic] ^= lmsk;
							wall_infP->wall_map[ic + 1] ^= rmsk;
							wall_infP->cat_inf[cat_id].cat_id = cat_id;
							wall_infP->cat_inf[cat_id].length = cat_width;
							wall_infP->cat_inf[cat_id].pos = (ic*MAXBITCNT) + (MAXBITCNT - rsb);
							break;
						}
						else{
							goto pgend;
						}
					}
				}
			}
			else{
				rsb = local_ntz(~(wall_infP->wall_map[ic]));
				lsb = local_nlz(~(wall_infP->wall_map[ic + 1]));
				if (first_ary == -1){
					lmsk = (BITMASK >> (MAXBITCNT - rsb));
					first_ary = ic;
				}
				if (rsb + lsb >= set_bits){
					lsb = set_bits - rsb;
					last_ary = ic + 1;
					rmsk = BITMASK << (MAXBITCNT - lsb);
					if (cat_width + ((first_ary*MAXBITCNT) + (MAXBITCNT - rsb)) <= w_width){
						wall_infP->wall_map[first_ary] ^= lmsk;
						wall_infP->wall_map[last_ary] ^= rmsk;
						for (jc = first_ary + 1; jc < last_ary; jc++){
							wall_infP->wall_map[jc] = 0;
						}
						wall_infP->cat_inf[cat_id].cat_id = cat_id;
						wall_infP->cat_inf[cat_id].length = cat_width;
						wall_infP->cat_inf[cat_id].pos = (first_ary*MAXBITCNT) + (MAXBITCNT - rsb);
						break;
					}
					else{
						goto pgend;
					}
				}
				if (lsb != MAXBITCNT || rsb == 0){
					/* ???????????????????????\??????????????? */
					set_bits = w_width;
					first_ary = -1;
				}
				else{
					set_bits -= rsb;
				}
			}
		}
		if (wall_infP->cat_inf[cat_id].cat_id == -1){
			// ???????????§??????
			ret = -1;
		}
		else{
			ret = wall_infP->cat_inf[cat_id].pos;
		}
		break;
	case	1:
		// ??????????±???¨?????????????±????
		first_ary = wall_infP->cat_inf[cat_id].pos >> SHIFTBITCNT;
		lsb = wall_infP->cat_inf[cat_id].pos - (first_ary << SHIFTBITCNT);
		last_ary = (wall_infP->cat_inf[cat_id].pos + (wall_infP->cat_inf[cat_id].length - 1)) >> SHIFTBITCNT;
		if (first_ary == last_ary){
			rsb = (BITMASK << (MAXBITCNT - wall_infP->cat_inf[cat_id].length));
			wall_infP->wall_map[first_ary] |= (rsb >> lsb);
		}
		else{
			rsb = (wall_infP->cat_inf[cat_id].pos + (wall_infP->cat_inf[cat_id].length - 1)) - (last_ary << SHIFTBITCNT);
			lmsk = BITMASK >> lsb;
			rmsk = BITMASK >> (rsb + 1);
			if (lmsk == 0){
				lmsk = BITMASK;
			}
			if (rmsk == BITMASK){
				rmsk = 0;
			}
			wall_infP->wall_map[first_ary] |= lmsk;
			wall_infP->wall_map[last_ary] |= ~rmsk;;
			for (ic = first_ary + 1; ic<last_ary; ic++){
				wall_infP->wall_map[ic] = BITMASK;
			}
		}
		wall_infP->cat_inf[cat_id].cat_id = -1;
		wall_infP->cat_inf[cat_id].pos = -1;
		wall_infP->cat_inf[cat_id].length = 0;
		ret = 0;
		break;
	}
pgend:
	return ret;
}

static	int count_bits(unsigned bits) {
	bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
	bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
	bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
	bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
	return (bits & 0x0000ffff) + (bits >> 16 & 0x0000ffff);
}

#define u 99
static	int local_nlz(unsigned x) {

	static char table[64] =
	{ 32, 31, u, 16, u, 30, 3, u, 15, u, u, u, 29, 10, 2, u,
	u, u, 12, 14, 21, u, 19, u, u, 28, u, 25, u, 9, 1, u,
	17, u, 4, u, u, u, 11, u, 13, 22, 20, u, 26, u, u, 18,
	5, u, u, 23, u, 27, u, 6, u, 24, 7, u, 8, u, 0, u };

	x = x | (x >> 1);    // Propagate leftmost
	x = x | (x >> 2);    // 1-bit to the right.
	x = x | (x >> 4);
	x = x | (x >> 8);
	x = x | (x >> 16);
	x = x * 0x06EB14F9;    // Multiplier is 7*255**3.
	return table[x >> 26];
}

static	int local_ntz(unsigned x) {
	if (x == 0) { return MAXBITCNT; }

	return(count_bits((~x)&(x - 1)));
}

static	int ffstr(unsigned x, int n) {
	int s;

	while (n > 1) {
		s = n >> 1;
		x = x & (x << s);
		n = n - s;
	}
	return local_nlz(x);
}

Compiler output:
a.cc:33:22: error: '_TCHAR' has not been declared
   33 | int _tmain(int argc, _TCHAR* argv[])
      |                      ^~~~~~
a.cc: In function 'int _tmain(int, int**)':
a.cc:46:9: error: 'fopen_s' was not declared in this scope; did you mean 'fopen64'?
   46 |         fopen_s(&fp,(char *)DATFILE, (char *)"r");
      |         ^~~~~~~
      |         fopen64
a.cc:49:23: error: 'strtok_s' was not declared in this scope; did you mean 'strtok_r'?
   49 |                 tok = strtok_s(Buf, " , ", &next_tok);
      |                       ^~~~~~~~
      |                       strtok_r