Submission #1271814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271814		kiteyu	Combo (IOI18_combo)	C++17	97 / 100	8 ms	528 KiB

combo

#include<bits/stdc++.h>
#include "combo.h"
using namespace std;
//using ll=long long;
//int pi[100005];
//string S;
//int cnt=0;
//int press(string st){
//    cnt++;
//    int len=0,best=0;
//    for(char c:st){
//        while(len>0&&(len>=(int)S.size()||S[len]!=c))len=pi[len-1];
//        if(len<(int)S.size()&&S[len]==c)len++;
//        best=max(best,len);
//        if(best==(int)S.size())break;
//    }
//    return best;
//}

string guess_sequence(int N){
    string st="";
    if(press("A")==1) st+='A';
    else if(press("B")==1) st+='B';
    else if(press("X")==1) st+='X';
    else st+='Y';
    if(N==1) return st;
    char c1, c2, c3;
    if(st[0]=='A')c1='B', c2='X', c3='Y';
    if(st[0]=='B')c1='A', c2='X', c3='Y';
    if(st[0]=='X')c1='B', c2='Y', c3='A';
    if(st[0]=='Y')c1='B', c2='X', c3='A';
    for(int i=1;i<=N-2;++i){
//       cout<<i<<','<<st<<"!\n";
        string tmp="";
        tmp+=st+c1;
        tmp+=st+c2+c1;
        tmp+=st+c2+c2;
        tmp+=st+c2+c3;
        int res = press(tmp);
//        cout<<tmp<<','<<res<<'\n';
        if(res==(int)st.size()+1) st+=c1;
        else if(res==(int)st.size()+2)st+=c2;
        else st+= c3;
    }
    string tmp ="";
    tmp+=st+c1;
    tmp+=st+c2;
    if(press(tmp)==N){
        tmp=st+c1;
        if(press(tmp)==N)st+=c1;
        else st+=c2;
    }
    else st+=c3;
    return st;
}

//int main(){
//    cin>>S;
//    int n = (int)S.size();
//    for(int i=1;i<n;++i){
//        int j=pi[i-1];
//        while(j>0&&S[i]!=S[j])j=pi[j-1];
//        if(S[i]==S[j])++j;
//        pi[i]=j;
//    }
//    cout<<guess_sequence(n);
//}

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