제출 #239644

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
239644		luciocf	Password (RMI18_password)	C++14	100 / 100	671 ms	684 KiB

password

#include <bits/stdc++.h>

using namespace std;

int query(string str);

int freq[27];
int nxt[5010];
int mark[5010];

string ans = "";

int qtd(int pos, char c)
{
	if (mark[pos] != -1) return mark[pos];

	string aux = "";

	for (int i = 0; i <= pos; i++)
		aux += ans[i];

	for (int i = 0; i < freq[(int)(c-'a')]; i++)
		aux += c;

	return mark[pos] = (query(aux) - (pos+1));
}

string guess(int n, int s)
{
	freq[s-1] = n;

	for (int i = 0; i < s-1; i++)
	{
		char c = (char)('a'+i);
		string aux = "";

		for (int j = 0; j < n; j++)
			aux += c;

		freq[i] = query(aux);
		freq[s-1] -= freq[i];
	}

	for (int i = 0; i < s; i++)
	{
		if (!freq[i]) continue;

		memset(nxt, 0, sizeof nxt);
		memset(mark, -1, sizeof mark);

		char c = (char)('a'+i);
		int tot = 0;

		if (ans.empty())
		{
			for (int j = 0; j < freq[i]; j++)
				ans += c;
			continue;
		}

		int last = ans.size()-1;

		while (true)
		{
			int ini = 0, fim = last, ind = -1;

			if (tot < freq[i] && qtd(0, c) > tot)
			{
				while (ini <= fim)
				{
					int mid = (ini+fim)>>1;

					if (qtd(mid, c) > tot) ind = mid, ini = mid+1;
					else fim = mid-1;
				}
			}

			if (ind == -1)
			{
				string aux = "";

				for (int j = 0; j < freq[i]-tot; j++)
					aux += c;

				for (int j = 0; j < ans.size(); j++)
				{
					aux += ans[j];

					for (int l = 0; l < nxt[j]; l++)
						aux += c;
				}
				swap(ans, aux);

				break;
			}

			nxt[ind] = qtd(ind, c)-tot;
			tot = qtd(ind, c);
			last = ind-1;
		}
	}

	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

password.cpp: In function 'std::__cxx11::string guess(int, int)':
password.cpp:85:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < ans.size(); j++)
                     ~~^~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 30 / 30
• Subtask 5: 20 / 20