Submission #1271806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271806		kiteyu	Combo (IOI18_combo)	C++17	0 / 100	0 ms	408 KiB

combo

#include<bits/stdc++.h>
#include "combo.h"
using namespace std;
using ll=long long;
const char dc[]={'A','B','X','Y'};
//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';

    for(int i=1;i<N;++i){
//        cout<<i<<','<<st<<"!\n";
        string tmp="";
        char c1='#',c2='#',c3='#';
        for(int j=0;j<4;++j)
            if(st[0]!=dc[j]){
                if(c1=='#')c1=dc[j];
                else if(c2=='#') c2=dc[j];
                else c3=dc[j];
            }
//        cout<<c1<<'_'<<c2<<'_'<<c3<<'\n';
        tmp+=st+c1;

        for(int j=0;j<4;++j)
            if(st[0]!=dc[j])
                tmp+=st+c2+dc[j];
        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;

    }
//    cout<<cnt<<"!\n";
    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: 0 / 5
• Subtask 2: 0 / 95