Submission #570322

#	Time	Username	Problem	Language	Result	Execution time	Memory
570322		web	Combo (IOI18_combo)	C++17	30 / 100	55 ms	612 KiB

combo

#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;
}

Compilation message (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)
      |        ~~~~~~~~~~~~~~~~~~~~~~~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 25 / 95