Submission #574943

#	Time	Username	Problem	Language	Result	Execution time	Memory
574943		Hackapie	Combo (IOI18_combo)	C++17	10 / 100	71 ms	608 KiB

combo

#include "combo.h"
#include<bits/stdc++.h>
using namespace std;
 
std::string guess_sequence(int N){
  set<char> s;
  s.insert('A');
  s.insert('B');
  s.insert('X');
  s.insert('Y');
  string res;
  vector<string> pr;
  for(int i=1;i<=N;i++){  //cout<<"i:"<<i<<"\n";
    //each i for ith character
    //in first i we have 4 choices 
    //afterthat we have 3 choices always
    char c;
    if(i==1){
        for(auto x:s){
            string aux=res;
            aux+=x;
            int ans=press(aux);
            // cout<<aux<<"\n";
            // int ans;
            // cin>>ans;
            if(ans==i){
                //ok this is part of the string 
                res=aux;
                c=x;
                break;
            }
        }
        if(i==1)s.erase(c);
        for(auto x:s){
            for(auto y:s){
                string p;
                p+=x;
                p+=y;
                pr.push_back(p);
            }
        }
        // cout<<"pr.size():"<<pr.size()<<"\n";
        // for(int i=0;i<pr.size();i++){
        //     cout<<pr[i]<<" ";
        // }  cout<<"\n";
    }else{
        if(i==N){
            for(auto x:s){
                string aux=res;
                aux+=x;
                int ans=press(aux);
                // cout<<aux<<"\n";
                // int ans;
                // cin>>ans;
                if(ans==i){
                    //ok this is part of the string 
                    res=aux;
                    break;
                }
            }
        }else{
            //query 2 at once 
            for(int k=0;k<9;k+=3){
                string aux=res;
                string pre=res;
                aux+=pr[k];
                aux+=pre;
                aux+=pr[k+1];
                aux+=pre;
                aux+=pr[k+2];
                int ans=press(aux);
                // cout<<aux<<"\n";
                // int ans;
                // cin>>ans;
                int ch=0;
                if(ans==i+1){
                    for(int j=k;j<k+3;j++){
                        string aux2=res;
                        aux2+=pr[j];
                        int ans=press(aux2);
                        // cout<<aux2<<"\n";
                        // cin>>ans;
                        if(ans==i+1){
                            res=aux2;
                            break;
                        }
                    }
                    ch=1;
                }
                if(ch==1)break;
            }
            i+=1;
        }
    }
 
  }
return res;
  //how can we bring down the number of presses more?
  //we get length of largest substring that is prefix of S
  //finding next 2 positions take 6 queries
  //can we bring it down?
  //we can do like *xy*yc in 1 query
  //*xc*cy in next
  //*yx*cx in next
  //*yy*xx*cc in next
  //then singularly everyother
  //this will in worst case take 7 queries if it is cc
  //what if all 3 3 
  //xy*yc*cy
  //xc*yx*cx
  //yy*xx*cc 
  //now in worst case 6 queries else it takes only 4 in best case 
  //use this to optimize a bit
}

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