이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <math.h>
#include "combo.h"
#include <set>
#include<vector>
#include <iostream>
#include<string>
using namespace std;
string findSPrefixLenL(int L, string str)
{
if(str.length() == L)
return str;
if((str.length()/L)%2 == 0)
{
if(press(str.substr(0, str.length()/2)) == L)
return findSPrefixLenL(L, str.substr(0, str.length()/2));
else
return findSPrefixLenL(L, str.substr(str.length()/2));
}
else
{
int midPoint = ((str.length()/L)/2)*L;
if(press(str.substr(0, midPoint))==L)
return findSPrefixLenL(L, str.substr(0, midPoint));
else
return findSPrefixLenL(L, str.substr(midPoint));
}
}
long long fastExp(int base, int exp)
{
if(exp == 1)
return base;
if(exp%2 ==0)
{
long long num = fastExp(base, exp/2);
return num*num;
}
else
{
return base*fastExp(base, exp-1);
}
}
int maxLookAhead(int currSizeS, int N)
{
int min = 1, max = N-currSizeS+1;
while(max-min > 1)
{
int midPoint = (max + min) /2;
if(midPoint >= (log2(4*N)/log2(3)))
{
max = midPoint;
continue;
}
else
{
if(static_cast<long long>((currSizeS+midPoint))*(fastExp(3,midPoint)) <= 4*N)
{
min = midPoint;
continue;
}
else
{
max = midPoint;
continue;
}
}
}
return min;
}
vector<vector<string>> possStringsSizeN = {{""}};
void calcAllStringsSizeN(int N, vector<char> letters)
{
if(possStringsSizeN.size() >= N+1)
return;
else
{
if(possStringsSizeN.size() < N)
{
calcAllStringsSizeN(N-1, letters);
}
possStringsSizeN.push_back({});
for(string& s : possStringsSizeN[N-1])
{
for(char l : letters)
{
possStringsSizeN[N].push_back(s + l);
}
}
}
}
string guess_sequence(int N) {
//find first letter
string p = "AB";
char firstLetter;
if(press(p))
{
if(press("A"))
firstLetter = 'A';
else
firstLetter = 'B';
}
else
{
if(press("X"))
firstLetter = 'X';
else
firstLetter = 'Y';
}
// cout<<firstLetter<<'\n';
set<char> usableLettersS = {'A','B','X','Y'};
usableLettersS.erase(firstLetter);
vector<char> usableLetters;
for(auto letter :usableLettersS)
usableLetters.push_back(letter);
string S = "";
S+= firstLetter;
//cout<<"startS: "<<S<<'\n';
for(int i = 1; i< N; )
{
// cout<<"entered with i = "<<i<<'\n';
int lookAhead = maxLookAhead(S.size(), N);
string p = "";
calcAllStringsSizeN(lookAhead, usableLetters);
/* cout<<"calculatedStrings:"<<'\n';
for(string& s:possStringsSizeN[lookAhead])
{
cout<<s<<'\n';
}
cout<<lookAhead<<'\n';*/
for(string& s:possStringsSizeN[lookAhead])
{
p += S + s;
//cout<<"poss Strng: "<<S+s<<'\n';
}
i+= lookAhead;
S = findSPrefixLenL(S.size() + lookAhead, p);
// cout<<"new S: "<<S<<'\n';
}
return S;
}
컴파일 시 표준 에러 (stderr) 메시지
combo.cpp: In function 'std::string findSPrefixLenL(int, std::string)':
combo.cpp:12:19: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
12 | if(str.length() == L)
| ~~~~~~~~~~~~~^~~~
combo.cpp: In function 'void calcAllStringsSizeN(int, std::vector<char>)':
combo.cpp:82:30: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<std::__cxx11::basic_string<char> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
82 | if(possStringsSizeN.size() >= N+1)
| ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
combo.cpp:86:32: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<std::__cxx11::basic_string<char> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
86 | if(possStringsSizeN.size() < N)
| ~~~~~~~~~~~~~~~~~~~~~~~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |