Submission #1139379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139379		davele	Combo (IOI18_combo)	C++20	5 / 100	0 ms	408 KiB

combo

#ifndef davele
#include "combo.h"
#endif // davele

#include <bits/stdc++.h>
#define pq priority_queue
#define ll long long
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(i) (1ll<<(i))
#define next __next
#define pos __pos
using namespace std;
const double PI = acos(-1);
/*const int mod = ;

void sub (int&a, const int&b){
    a-=b;
    if (a<0) a+=mod;
}

void mul (int&a, const int&b){
    a = (1ll*a*b)%mod;
}

void add (int&a, const int&b){
    a+=b;
    if (a>=mod) a-=mod;
}*/

bool minimize (ll&a, const ll&b){
    if (a<=b) return false;
    a=b;
    return true;
}

bool maximize (ll&a, const ll&b){
    if (a>=b) return false;
    a=b;
    return true;
}
////////////////////////////////////////////////////////////////////////////////////////////

string tt[4];

#ifndef davele


string guess_sequence(int n) {
    if (n>5) assert(0==1);
    tt[0] = "A"; tt[1] = "B"; tt[2] = "X"; tt[3] = "Y";
    int startletter;
    if (press(tt[0]+tt[1])){
        if (press(tt[0])) startletter = 0;
        else startletter = 1;
    }
    else{
        if (press(tt[2])) startletter = 2;
        else startletter = 3;
    }
    string ret = tt[startletter];
    string cur[3];
    int len = 0;
    for (int i=0; i<4; i++) if (i!=startletter) cur[len++] = tt[i];
    for (int i=1; i+1<n; i++){
        int get = press(ret+cur[0]+ret+cur[1]+cur[0]+ret+cur[1]+cur[1]+ret+cur[1]+cur[2]);
        if (get==i){
            ret+=cur[2];
        }
        else if (get==i+1) ret+=cur[0];
        else ret+=cur[1];
    }
    if (press(ret+cur[0])==n) return (ret+cur[0]);
    else if (press(ret+cur[1])==n) return (ret+cur[1]);
    return (ret+cur[2]);
}

#endif // davele

#ifdef davele
string s;
int N, tot = 0;

int press(const string&p){
    tot++;
//    cerr<<N<<" "<<p.size()<<"\n";
    if (p.size()>N*4){
        cerr<<"FALSSEESS"<<"\n";
    }
    int coins = 0;
  int len = p.length();
  for (int i = 0, j = 0; i < len; ++i) {
    if (j < N && s[j] == p[i]) {
      ++j;
    } else if (s[0] == p[i]) {
      j = 1;
    } else {
      j = 0;
    }
    coins = std::max(coins, j);
  }
  return coins;
}

string guess_sequence(int n) {
    tt[0] = "A"; tt[1] = "B"; tt[2] = "X"; tt[3] = "Y";
    int startletter;
    if (press(tt[0]+tt[1])){
        if (press(tt[0])) startletter = 0;
        else startletter = 1;
    }
    else{
        if (press(tt[2])) startletter = 2;
        else startletter = 3;
    }
    string ret = tt[startletter];
    string cur[3];
    int len = 0;
    for (int i=0; i<4; i++) if (i!=startletter) cur[len++] = tt[i];
    for (int i=1; i+1<n; i++){
        int get = press(ret+cur[0]+ret+cur[1]+cur[0]+ret+cur[1]+cur[1]+ret+cur[1]+cur[2]);
        if (get==i){
            ret+=cur[2];
        }
        else if (get==i+1) ret+=cur[0];
        else ret+=cur[1];
    }
    if (press(ret+cur[0])==n) return (ret+cur[0]);
    else if (press(ret+cur[1])==n) return (ret+cur[1]);
    return (ret+cur[2]);
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    freopen("combo.inp", "r", stdin);
    freopen("combo.out", "w", stdout);
    cin>>s;
    N = s.size();
//    cerr<<N<<"\n";
    cout<<guess_sequence(N);
//    cerr<<"\n"<<tot;
}
#endif // davele

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