Submission #647860

#	Time	Username	Problem	Language	Result	Execution time	Memory
647860		ansgar	Combo (IOI18_combo)	C++17	97 / 100	43 ms	596 KiB

combo

#include <bits/stdc++.h>
#include <combo.h>
using namespace std;

//#define int long long
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define vb vector<bool>
#define vc vector<char>
#define vvc vector<vc>
#define vvb vector<vb>
#define si set<int>
#define mii map<int,int>

const int mod=1e9+7;
const int N=2e5+1;

int fact[N],frev[N],s[N],l[N];
bool P[N];
vi primes;
vvi G;
vb B;

int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
int mcm(int a,int b){
    return (a*b)/gcd(a,b);
}
int poW(int a,int p){
    if(p==0)return 1;
    if(p==1)return a;
    return poW(a*a%mod,p/2)*(p%2?a:1)%mod;
}
bool prime(int n){
    if(n<=1)return false;
    for(int i=2;i*i<=n;i++){
        if(n%i==0)return false;
    }
    return true;
}
void initfact(){
    fact[0]=fact[1]=frev[0]=frev[1]=1;
    for(int i=2;i<N;i++){
        fact[i]=i*fact[i-1]%mod;
        frev[i]=poW(fact[i],mod-2);
    }
}
int choose(int n,int k){
    if(n<k)return 0;
    return (fact[n]*frev[k]%mod)*frev[n-k]%mod;
}
void initPrimes(){
    memset(P,true,sizeof(P));
    P[0]=P[1]=false;
    for(int i=2;i<N;i++){
        if(P[i]){
            primes.push_back(i);
            for(int j=i*2;j<N;j+=i){
                P[j]=false;
            }
        }
    }
}
void resetdsu(){
    for(int i=0;i<N;i++){
        s[i]=1;
        l[i]=i;
    }
}
int find(int x){
    while(x!=l[x])x=l[x];
    return x;
}
bool same(int a,int b){
    return find(a)==find(b);
}
void unite(int a,int b){
    a=find(a);
    b=find(b);
    if(s[a]<s[b])swap(a,b);
    l[b]=a;
    s[a]+=s[b];
}
void dfs(int u){
    B[u]=true;
    for(int v : G[u]){
        if(!B[v]){
            dfs(v);
        }
    }
}
/*int press(string s){
    cout<<s<<endl;
    int x;
    cin>>x;
    return x;
}*/
string guess_sequence(int n){
    char f;
    string sol="";
    if(press("A")==1){
        sol="A";
        f='A';
    }
    else if(press("B")==1){ //YBXBX
        sol="B";
        f='B';
    }
    else if(press("X")==1){
        sol="X";
        f='X';
    }
    else{
        sol="Y";
        f='Y';
    }
    if(n==1)return sol;
    for(int i=1;i<n-1;i++){
        if(f=='A'){
            string aux=sol+"B"+sol+"XB"+sol+"XX"+sol+"XY";
            int val=press(aux);
            if(val==i+0){
                sol.push_back('Y');
            }
            else if(val==i+1){
                sol.push_back('B');
            }
            else sol.push_back('X');
        }
        if(f=='B'){
            string aux=sol+"A"+sol+"XA"+sol+"XX"+sol+"XY";
            int val=press(aux);
            if(val==i+0){
                sol.push_back('Y');
            }
            else if(val==i+1){
                sol.push_back('A');
            }
            else sol.push_back('X');
        }
        if(f=='X'){
            string aux=sol+"B"+sol+"AB"+sol+"AA"+sol+"AY";
            int val=press(aux);
            if(val==i+0)sol.push_back('Y');
            else if(val==i+1)sol.push_back('B');
            else sol.push_back('A');
        }
        if(f=='Y'){
            string aux=sol+"B"+sol+"XB"+sol+"XX"+sol+"XA";
            int val=press(aux);
            if(val==i+0)sol.push_back('A');
            else if(val==i+1)sol.push_back('B');
            else sol.push_back('X');
        }
    }
    if(f=='A'){
        string aux=sol+"B"+sol+"X";
        int val=press(aux);
        if(val==n-1){
            sol.push_back('Y');
            return sol;
        }
        else{
            aux=sol+"B";
            val=press(aux);
            if(val==n-1){
                sol.push_back('X');
                return sol;
            }
            else{
                sol.push_back('B');
                return sol;
            }
        }
    }
    
    if(f=='B'){
        string aux=sol+"A"+sol+"X";
        int val=press(aux);
        if(val==n-1){
            sol.push_back('Y');
            return sol;
        }
        else{
            aux=sol+"A";
            val=press(aux);
            if(val==n-1){
                sol.push_back('X');
                return sol;
            }
            else{
                sol.push_back('A');
                return sol;
            }
        }
    }

    if(f=='X'){
        string aux=sol+"B"+sol+"A";
        int val=press(aux);
        if(val==n-1){
            sol.push_back('Y');
            return sol;
        }
        else{
            aux=sol+"B";
            val=press(aux);
            if(val==n-1){
                sol.push_back('A');
                return sol;
            }
            else{
                sol.push_back('B');
                return sol;
            }
        }
    }
    
    string aux=sol+"B"+sol+"X";
        int val=press(aux);
        if(val==n-1){
            sol.push_back('A');
            return sol;
        }
            aux=sol+"B";
            val=press(aux);
            if(val==n-1){
                sol.push_back('X');
                return sol;
            }
                sol.push_back('B');
                return sol; //XBYAB
}
/*signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    cout<<guess_sequence(n);
}*/

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