QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#30952#3793. Killer PuzzleQingyuAC ✓5ms3780kbC++2317.5kb2022-05-02 12:26:082022-05-02 12:26:11

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-02 12:26:11]
  • Judged
  • Verdict: AC
  • Time: 5ms
  • Memory: 3780kb
Show
  • [2022-05-02 12:26:08]
  • Submitted

answer

/*
 * Task: Killer Puzzle
 * Submitter: Qingyu Shi
 * Submit Time: 2019.11.23 19:26:55
 * Verdict: OK
 */
#include <cstdio>
#include <string>
#include <iostream>
#include <cstdint>
#include <vector>
#include <stack>
#include <cmath>

int32_t n, m;
typedef long double real_t;

namespace Debugger
{
	inline void testInput();
}
namespace Solve
{
	enum Type
	{
		integer,
		string,
		boolean,
		function,
		error
	};
}
namespace IO
{
	constexpr int SIZE = (1 << 16) - 1;
	inline std::string getLine()
	{
		static char s[SIZE];
		scanf(" %[^\n]s", s);
		return std::string(s);
	}
}
namespace Judger
{
	inline bool endpos(const char c)
	{
		return c == '\0';
	}
	inline bool emptyChar(const char c)
	{
		return c == ' ' || c == '\r' || c == '\n' || c == '\0';
	}
	inline bool digitChar(const char c)
	{
		return c >= 48 && c <= 57;
	}
	inline bool checkConstant(const int32_t c)
	{
		return c == Solve::integer || c == Solve::string;
	}
	inline bool isPerfectSquare(const int32_t c)
	{
		if (c < 0) return false;
		int32_t x = sqrtl(c);
		return (x * x == c) || ((x + 1) * (x + 1) == c) || ((x - 1) * (x - 1) == c);
	}
	inline bool isPerfectCube(const int32_t c)
	{
		int32_t x = powl(c, 1.0L / 3);
		return (x * x * x == c) || ((x + 1) * (x + 1) * (x + 1) == c) || ((x - 1) * (x - 1) * (x - 1) == c);
	}
	inline bool isPrime(const int32_t c)
	{
		if (c <= 1) return false;
		if (c == 2) return true;
		if (c % 2 == 0) return false;
		for (int32_t i = 3; i * i <= c; i += 2)
		{
			if (c % i == 0)
			{
				return false;
			}
		}
		return true;
	}
	inline bool isFactor(const int32_t c)
	{
		int64_t r = 1;
		for (int32_t i = 1; ; ++i)
		{
			r *= i;
			if (r == c) return true;
			if (r > c) return false;
		}
		return false;
	}
	inline std::string to_lower(const std::string s)
	{
		std::string t = s;
		int32_t length = s.length();
		for (int i = 0; i < length; ++i) t[i] = tolower(s[i]);
		return t;
	}
	inline bool isVowel(const std::string s)
	{
		std::string t = to_lower(s);
		if (!isalpha(t[0])) return false;
		return t.size() == 1 && ((t == "a") || (t == "e") || (t == "i") || (t == "o") || (t == "u")); 
	}
	inline bool isConsonant(const std::string s)
	{
		if (!isalpha(s[0])) return false;
		return s.size() == 1 && !isVowel(s);
	}
	inline bool isMultiple(int32_t x, int32_t y)
	{
		if (x == 0 && y == 0) return true;
		if (y == 0) return false;
		if (x % y == 0) return true;
		return false;
	}
}

namespace Solve
{
	constexpr int COUNT = 12;
	struct Data
	{
		Type data_type;
		std::string data;
		int32_t info;
		Data(Type data_type, std::string data, int32_t info) : data_type(data_type), data(data), info(info)
		{
			
		}
	} ERR(error, "", NULL), trueData(boolean, "", true), falseData(boolean, "", false);
	struct Question
	{
		std::vector<Data> answers[6];
		std::vector<int32_t> trans[6];
	} Q[COUNT];
	
	// Section A. Input
	
	inline void loadData(std::vector<Data> &judge, std::vector<int32_t> &trans, std::string strInfo)
	{
		std::stack<int> expStack;
		for (int i = 0; !Judger::endpos(strInfo[i]); ++i)
		{
			if (!Judger::emptyChar(strInfo[i]))
			{
				if (strInfo[i] == '\"') // Case 1: Typeof(datum) == string
				{
					std::string datum = "";
					trans.push_back(-1);
					++i;
					while (strInfo[i] != '\"')
					{
						datum += strInfo[i++];
					}
					judge.push_back(Data(string, datum, NULL));
				}
				else if (Judger::digitChar(strInfo[i])) // Case 2: Typeof(datum) == int_t
				{
					int32_t datum = 0;
					trans.push_back(-1);
					while (Judger::digitChar(strInfo[i]))
					{
						datum = datum * 10 + strInfo[i++] - 48;
					}
					judge.push_back(Data(integer, "", datum));
					--i;
				}
				else if (strInfo[i] == '(') // Case 3A
				{
					judge.push_back(Data(function, "(", NULL));
					trans.push_back(-1);
					expStack.push(trans.size() - 1);
				}
				else if (strInfo[i] == ')') // Case 3B
				{
					judge.push_back(Data(function, ")", NULL));
					trans.push_back(-1);
					trans[expStack.top()] = trans.size() - 1;
					expStack.pop();
				}
				else // Case 4
				{
					std::string datum = "";
					trans.push_back(-1);
					while (!Judger::emptyChar(strInfo[i]) && strInfo[i] != '(' && strInfo[i] != ')')
					{
						datum += strInfo[i++];
					}
					--i;
					judge.push_back(Data(function, datum, NULL));
				}
			}
		}
	}
	
	// Section B. Functions
	
	Data invokePred(std::vector<Data> &, std::vector<int32_t> &, int32_t, int32_t, Data);
	Data invokeFunction(std::vector<Data> &, std::vector<int32_t> &, int32_t, int32_t);
	std::vector<Data> now_answer;
	std::vector<int32_t> now_trans;
	char answerList[16];

	Data invokePred(std::vector<Data> &answers, std::vector<int32_t> &trans, int32_t L, int32_t R, Data pred)
	{
		std::vector<std::pair<int32_t, int32_t> > arguments;
		arguments.clear();
		
		// Skip all '(' && ')'
		while (trans[L] == R)
		{
			++L; --R;
		}
		if (L == R && Judger::checkConstant(answers[L].data_type)) 
		{
			return answers[L]; 
		}
		// Get arguments
		int32_t oldL = L++;
		while (L <= R)
		{
			int32_t last = L;
			if (trans[L] != -1) last = trans[L];
			arguments.push_back(std::make_pair(L, last));
			L = last + 1;
		}
		L = oldL;
		
		// Calculating the functions.
		std::string funcName = answers[L].data;
		// PartA: Pure pred.
		if (funcName == "prime-p")
		{
			if (pred.data_type != integer) return ERR;
			return Data(boolean, "", Judger::isPrime(pred.info));
		}
		else if (funcName == "factorial-p")
		{
			if (pred.data_type != integer) return ERR;
			return Data(boolean, "", Judger::isFactor(pred.info));
		}
		else if (funcName == "square-p")
		{
			if (pred.data_type != integer) return ERR;
			return Data(boolean, "", Judger::isPerfectSquare(pred.info));
		}
		else if (funcName == "cubic-p")
		{
			if (pred.data_type != integer) return ERR;
			return Data(boolean, "", Judger::isPerfectCube(pred.info));
		}
		else if (funcName == "vowel-p")
		{
			if (pred.data_type != string) return ERR;
			return Data(boolean, "", Judger::isVowel(pred.data));
		}
		else if (funcName == "consonant-p")
		{
			if (pred.data_type != string) return ERR;
			return Data(boolean, "", Judger::isConsonant(pred.data));
		}
		// Part B: opt.
		else if (funcName == "option-value")
		{
			return invokePred(now_answer, now_trans, 0, now_answer.size() - 1, pred);
		}
		// Part C: pred maker.
		else if (funcName == "make-answer-diff-next-equal")
		{
			if (pred.data_type != integer) return ERR;
			if (pred.info <= 0 || pred.info >= n) return ERR; // 1 <= pred_info, pred_info + 1 <= N => 0 < pred_info < N
			Data __arg = invokeFunction(answers, trans, arguments[0].first, arguments[0].second);
			if (__arg.data_type != integer) return ERR;
			int32_t __distance = abs(answerList[pred.info] - answerList[pred.info + 1]);
			return Data(boolean, "", __distance == __arg.info);
		}
		else if (funcName == "make-answer-equal")
		{
			if (pred.data_type != integer) return ERR; // (answer idx) will throw an exception.
			if (pred.info <= 0 || pred.info > n) return ERR;
			Data __arg = invokeFunction(answers, trans, arguments[0].first, arguments[0].second);
			return Data(boolean, "", __arg.data.size() == 1 && __arg.data[0] == answerList[pred.info]);
		}
		else if (funcName == "make-answer-is")
		{
			if (pred.data_type != integer) return ERR; // (answer idx) will throw an exception.
			if (pred.info <= 0 || pred.info > n) return ERR;
			std::string transformed = ""; transformed += answerList[pred.info];
			Data __arg = invokePred(answers, trans, arguments[0].first, arguments[0].second, 
							Data(string, transformed, NULL));
			return Data(boolean, "", __arg.data_type == boolean && __arg.info == true);
		}
		else if (funcName == "make-answer-value-equal")
		{
			if (pred.data_type != integer) return ERR; // (answer-value idx) will throw an exception.
			if (pred.info <= 0 || pred.info > n) return ERR;
			std::vector<Data> &temp_answer = Q[pred.info].answers[answerList[pred.info] - 'a' + 1];
			std::vector<int32_t> &temp_trans = Q[pred.info].trans[answerList[pred.info] - 'a' + 1];
			Data __arg = invokeFunction(answers, trans, arguments[0].first, arguments[0].second),
				 __val = invokeFunction(temp_answer, temp_trans, 0, temp_answer.size() - 1);
			return Data(boolean, "", __arg.data_type == __val.data_type
									&& __arg.info == __val.info
									&& __arg.data == __val.data);
		}
		else if (funcName == "make-answer-value-is")
		{
			if (pred.data_type != integer) return ERR;
			if (pred.info <= 0 || pred.info > n) return ERR;
			std::vector<Data> &temp_answer = Q[pred.info].answers[answerList[pred.info] - 'a' + 1];
			std::vector<int32_t> &temp_trans = Q[pred.info].trans[answerList[pred.info] - 'a' + 1];
			Data __val = invokeFunction(temp_answer, temp_trans, 0, temp_answer.size() - 1);
			Data result = invokePred(answers, trans, arguments[0].first, arguments[0].second, __val);
			return Data(boolean, "", result.data_type == boolean && result.info == true);
		}
		else if (funcName == "make-is-multiple")
		{
			if (pred.data_type != integer) return ERR;
			Data result = invokeFunction(answers, trans, arguments[0].first, arguments[0].second);
			if (result.data_type != integer)return ERR;
			return Data(boolean, "", Judger::isMultiple(pred.info, result.info));
		}
		else if (funcName == "make-equal")
		{
			Data result = invokeFunction(answers, trans, arguments[0].first, arguments[0].second);
			if (result.data_type != integer && result.data_type != string) return ERR;
			return Data(boolean, "", result.data_type == pred.data_type
									&& result.info == pred.info
									&& result.data == pred.data);
		}
		else if (funcName == "make-not")
		{
			Data result = invokePred(answers, trans, arguments[0].first, arguments[0].second, pred);
			if (result.data_type == boolean && !result.info)
			{
				return trueData;
			}
			else
			{
				return falseData;
			}
		}
		else if (funcName == "make-and")
		{
			Data result1 = invokePred(answers, trans, arguments[0].first, arguments[0].second, pred);
			if (result1.data_type != boolean || result1.info != true)
			{
				return falseData;
			}
			Data result2 = invokePred(answers, trans, arguments[1].first, arguments[1].second, pred);
			if (result2.data_type != boolean || result2.info != true) 
			{
				return falseData;
			}
			else
			{
				return trueData;
			}
		}
		else if (funcName == "make-or")
		{
			Data result1 = invokePred(answers, trans, arguments[0].first, arguments[0].second, pred);
			if (result1.data_type != boolean) return falseData;
			Data result2 = invokePred(answers, trans, arguments[1].first, arguments[1].second, pred);
			if (result1.data_type == boolean && result2.data_type == boolean && (result1.info == true || result2.info == true))
			{
				return trueData;
			}
			else 
			{
				return falseData;
			}
		}
		return ERR;
	}
	Data invokeFunction(std::vector<Data> &answers, std::vector<int32_t> &trans, int32_t L, int32_t R)
	{
		std::vector<std::pair<int32_t, int32_t> > arguments;
		arguments.clear();
		// Skip all paied "(" and ")"
		while (trans[L] == R)
		{
			++L;
			--R;
		}
		if (L == R && (answers[L].data_type == integer || answers[L].data_type == string))
		{
			return answers[L];
		}
		if (answers[L].data_type == function && answers[L].data == "(")
		{
			// answers[L] is actually just a pred.
			int32_t argumentLeft = trans[L] + 1, argumentRight = argumentLeft;
			if (trans[argumentRight] != -1)
			{
				argumentRight = trans[argumentRight];
			}
			Data pred = invokeFunction(answers, trans, argumentLeft, argumentRight);
			return invokePred(answers, trans, L + 1, trans[L] - 1, pred);
		}
		
		// Get arguments.
		int32_t oldL = L++;
		while (L <= R)
		{
			int32_t last = L;
			if (trans[last] != -1) last = trans[last];
			arguments.push_back(std::make_pair(L, last));
			L = last + 1;
		}
		L = oldL;
		std::string funcName = answers[L].data;
		if (funcName == "answer")
		{
			Data __arg = invokeFunction(answers, trans, arguments[0].first, arguments[0].second);
			if (__arg.data_type != integer) return ERR;
			if (__arg.info <= 0 || __arg.info > n) return ERR;
			std::string transformed = ""; transformed += answerList[__arg.info];
			return Data(string, transformed, NULL);
		}
		else if (funcName == "option-value")
		{
			return invokeFunction(now_answer, now_trans, 0, now_answer.size() - 1);
		}
		else if (funcName == "equal")
		{
			Data result1 = invokeFunction(answers, trans, arguments[0].first, arguments[0].second),
				 result2 = invokeFunction(answers, trans, arguments[1].first, arguments[1].second);
			if (result1.data_type == error || result2.data_type == error) return ERR;
			return Data(boolean, "", result1.data_type == result2.data_type
									&& result1.info == result2.info
									&& result1.data == result2.data);
		}
		else if (funcName == "answer-value")
		{
			Data __arg = invokeFunction(answers, trans, arguments[0].first, arguments[0].second);
			if (__arg.data_type != integer) return ERR;
			if (__arg.info <= 0 || __arg.info > n) return ERR;
			std::vector<Data> &temp_answer = Q[__arg.info].answers[answerList[__arg.info] - 'a' + 1];
			std::vector<int32_t> &temp_trans = Q[__arg.info].trans[answerList[__arg.info] - 'a' + 1];
			return invokeFunction(temp_answer, temp_trans, 0, temp_answer.size() - 1);
		}
		else if (funcName == "first-question")
		{
			for (int32_t i = 1; i <= n; ++i)
			{
				Data result = invokePred(answers, trans, arguments[0].first, arguments[0].second, Data(integer, "", i));
				if (result.data_type == boolean && result.info == true)
				{
					return Data(integer, "", i);
				}
			}
			return ERR;
		}
		else if (funcName == "last-question")
		{
			for (int32_t i = n; i >= 1; --i)
			{
				Data result = invokePred(answers, trans, arguments[0].first, arguments[0].second, Data(integer, "", i));
				if (result.data_type == boolean && result.info == true)
				{
					return Data(integer, "", i);
				}
			}
			return ERR;
		}
		else if (funcName == "only-question")
		{
			int32_t solution = 0;
			for (int32_t i = 1; i <= n; ++i)
			{
				Data result = invokePred(answers, trans, arguments[0].first, arguments[0].second, Data(integer, "", i));
				if (result.data_type == boolean && result.info == true)
				{
					if (solution != 0)
					{
						return ERR;
					}
					else
					{
						solution = i;
					}
				}
			}
			if (solution != 0)
			{
				return Data(integer, "", solution);
			}
			return ERR;
		}
		else if (funcName == "count-question")
		{
			int32_t count = 0;
			for (int32_t i = 1; i <= n; ++i)
			{
				Data result = invokePred(answers, trans, arguments[0].first, arguments[0].second, Data(integer, "", i));
				if (result.data_type == boolean && result.info == true)
				{
					++count;
				}
			}
			return Data(integer, "", count);
		}
		else if (funcName == "diff-answer")
		{
			Data result1 = invokeFunction(answers, trans, arguments[0].first, arguments[0].second);
			if (result1.info <= 0 || result1.info > n || result1.data_type != integer) 
			{
				return ERR;
			}
			Data result2 = invokeFunction(answers, trans, arguments[1].first, arguments[1].second);
			if (result2.info <= 0 || result2.info > n || result2.data_type != integer) 
			{
				return ERR;
			}
			return Data(integer, "", abs(answerList[result1.info] - answerList[result2.info]));
		}
		return ERR;
	}
	
	inline void Init()
	{
		for (int32_t i = 1; i <= n; ++i)
		{
			// Clear
			for (int32_t j = 0; j <= m; ++j) Q[i].answers[j].clear(), Q[i].trans[j].clear();
			// Read
			for (int32_t j = 0; j <= m; ++j)
			{
				std::string strInfo = IO::getLine();
				loadData(Q[i].answers[j], Q[i].trans[j], strInfo + "    ");
			}
		}
		// Debugger::testInput();
	}
	inline bool judge_option(Data __result)
	{
		return __result.data_type == boolean && __result.info == true;
	}
	inline void writeAnswer(const char *s)
	{
		printf("%s\n", s);
	}
	inline void checkAnswer(const char *s)
	{
		for (int32_t i = 1; i <= n; ++i)
		{
			for (int32_t j = 1; j <= m; ++j)
			{
				now_answer = Q[i].answers[j];
				now_trans = Q[i].trans[j];
				// Case 1: This option is "none-of-above"
				if (j != m || Q[i].answers[j].size() > 1 || Q[i].answers[j][0].data != "none-of-above")
				{
					// Case 2: This option has been selected, so it must be correct.
					if (j - 1 == s[i] - 'a' && 
						!judge_option(invokeFunction(Q[i].answers[0], Q[i].trans[0], 0, Q[i].answers[0].size() - 1)))
					{
						return;
					}
					// Case 3: This option must be incorrect.
					if (j - 1 != s[i] - 'a' && 
						judge_option(invokeFunction(Q[i].answers[0], Q[i].trans[0], 0, Q[i].answers[0].size() - 1)))
					{
						return;
					}
				}
			}
		}
		writeAnswer(s + 1);
	}
	void DFS(int32_t x)
	{
		if (x == n + 1)
		{
			answerList[n + 1] = '\0';
			checkAnswer(answerList);
		}
		else
		{
			for (int32_t i = 0; i < m; ++i)
			{
				answerList[x] = i + 'a';
				DFS(x + 1);
			}
		}
	}
}

namespace Debugger
{
	inline void testInput()
	{
		for (int32_t i = 1; i <= n; ++i)
		{
			for (int32_t j = 0; j <= m; ++j)
			{
				for (auto v : Solve::Q[i].answers[j]) printf("[%s, %d] ", v.data.c_str(), v.info);
				putchar('\n');
				for (auto v : Solve::Q[i].trans[j]) printf("%d ", v);
				putchar('\n');
			}
			putchar('\n');
		}
	}
}

int main()
{
	int32_t Case = 0;
	while (scanf("%d%d", &n, &m) != EOF)
	{
		printf("Case %d:\n", ++Case);
		Solve::Init();
		Solve::DFS(1);
	}
	return 0;
}
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 3780kb

input:

3 3
(equal (option-value) (count-question (make-answer-equal "a")))
3
0
1

(equal (option-value) "a")
"c"
"b"
"a"

((option-value) (count-question (make-answer-equal "c")))
(make-and (make-is-multiple 2) (make-or factorial-p prime-p))
(make-not prime-p)
"none-of-above"

3 2
(equal (option-value) (an...

output:

Case 1:
bcb
cca
Case 2:
aab
Case 3:
aba
Case 4:
ab
ee
Case 5:
abaa
Case 6:
bba
Case 7:
babbab
Case 8:
bbb
Case 9:
aba
Case 10:
cab
Case 11:
bba
Case 12:
caaac
ccaac
Case 13:
bba
Case 14:
abbab
Case 15:
bac
Case 16:
abb
Case 17:
abbac
Case 18:
baab
Case 19:
accb
Case 20:
bba
Case 21:
aab
Case 22:
bba...

result:

ok 79 lines
English 繁體中文 简体中文

Server Time: 2025-02-08 13:29:37 | OpenSource Project