// (C) Sologub Radu
#include <iostream>
#include <cmath>
#include <vector>
#include <fstream>
#include <algorithm>
#include <iomanip> // for std::setw and std::setfill
#include <map>
#include <chrono>
using namespace std;
const bool fileInput = true;
istream& input = *(fileInput ? new fstream("./input.in") : &cin);
// https://rmi.lbi.ro/rmi_2018/aj password
// Mock password for testing purposes
string actualPassword = "aaa";
int longestPrefixSubsequenceLength(const std::string& input1, const std::string& input2) {
int len1 = input1.length();
int len2 = input2.length();
// Two pointers to keep track of the characters in both strings
int i = 0; // Pointer for input1 (prefix)
int j = 0; // Pointer for input2 (source for subsequence)
// Iterate over the characters in both strings
while (i < len1 && j < len2) {
// If the characters match, move the pointer in input1
if (input1[i] == input2[j]) {
i++;
}
// Always move the pointer in input2
j++;
}
// The value of i gives us the length of the longest prefix
return i;
}
int query( string str) ;
string guess(int len, int alphabet){
string guess = "a";
// first char guess
while(query(guess) != 1){
guess[0]++;
}
forward_looking:
// forward looking
char forwardGuess = 'a';
while(query(guess + forwardGuess) < guess.size() + 1 && forwardGuess < 'a' + alphabet){
forwardGuess++;
}
if(forwardGuess >= 'a' + alphabet){
// failed forward look, skip;
}else{
// success
guess = guess + forwardGuess;
// cout << guess << endl;
goto forward_looking;
}
int backInsertIndex = guess.size();
back_inserter:
if(guess.size() == len){
return guess;
}
string backGuess = "a";
backGuess[0]--;
string guessTry;
do{
guessTry = guess;
backGuess[0]++;
guessTry.insert(backInsertIndex, backGuess);
// cout << "guessTry = " << guessTry << endl;
}while(backGuess[0] < 'a' + alphabet
&& query(guessTry) < guess.size() + 1);
if(backGuess[0] >= 'a' + alphabet){
// failed back insert at index;
backInsertIndex --;
if(backInsertIndex < 0){
backInsertIndex = guess.size() - 1;
}
}else{
// success
// backInsertIndex --;
guess = guess.insert(backInsertIndex, backGuess);
// cout << guess << endl;
}
goto back_inserter;
}
int main(){
auto start = std::chrono::high_resolution_clock::now();
int L, Alpha;
input >> L >> Alpha;
input >> actualPassword;
// cout << actualPassword << endl << endl;
cout << guess(L, Alpha) << endl;
auto end = std::chrono::high_resolution_clock::now();
// Calculate the duration in milliseconds
std::chrono::duration<double, std::milli> duration = end - start;
// Output the duration
std::cout << "Execution time: " << duration.count() << " ms" << std::endl;
}
Compilation message
password.cpp: In function 'std::string guess(int, int)':
password.cpp:56:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | while(query(guess + forwardGuess) < guess.size() + 1 && forwardGuess < 'a' + alphabet){
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
password.cpp:72:21: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
72 | if(guess.size() == len){
| ~~~~~~~~~~~~~^~~~~~
password.cpp:86:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | && query(guessTry) < guess.size() + 1);
| ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccmKckPB.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccKQi9CC.o:password.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
