Submission #378923

#	Time	Username	Problem	Language	Result	Execution time	Memory
378923		jisnu	Combo (IOI18_combo)	C++11	30 / 100	46 ms	572 KiB

combo

#include "combo.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl '\n'
#define INF 1e9+7
#define all(x) x.begin(),x.end()

using namespace std;
using namespace __gnu_pbds;
using pii=pair<int,int>;
using ppi=pair<int,pii>;
using ll=long long;
using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;

void _print(vector<pii> x) {cerr<<"["; for(auto e:x) cerr<<"{"<<e.first<<","<<e.second<<"} ,"; cerr<<"]";}
template<typename T>
void _print(vector<T> x) {cerr<<"{"; for(auto e:x) cerr<<e<<","; cerr<<"}";}
void _print(pii x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(T x) {cerr<<x;}
void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
    _print(H);
    if(sizeof...(T)) cerr<<",";
    else cerr<<"]";
    dbg(T...);
}
#define debug(...) cerr<<"[\""<<#__VA_ARGS__<<"\"]: [",dbg(__VA_ARGS__);

char a[4]={'A','B','X','Y'};
vector<char> ar;

std::string guess_sequence(int N) {
//    debug(N);
    string ans;
    for(int i=0;i<3;i++) {
        string temp; temp.push_back(a[i]);
        int res=press(temp);
        if(res==1) {
           ans+=a[i]; break;
        }
    }
    if(ans.empty()) ans.push_back(a[3]);

    for(int i=0;i<4;i++) {
        if(a[i]!=ans[0]) ar.push_back(a[i]);
    }
    bool past=false;
    vector<char> past_list;
    vector<string> guess_list;
    for(auto e:ar) {
        for(auto f:ar) {
            string temp; temp.push_back(e); temp.push_back(f);
            guess_list.push_back(temp);
        }
    }
//    debug(guess_list);
    for(int i=2;i<=N;i++) {
        int len=ans.size();
        if(past) {
            if(i==N) {
                string temp=ans; temp.push_back(past_list[0]);
                if(press(temp)==N) return temp;
                ans.push_back(past_list[1]);
                return ans;
            }
            else {
                string temp;
                for(int j=0;j<2;j++) {
                    temp+=ans; temp.push_back(past_list[0]);
                    temp.push_back(ar[j]);
                }
                int res=press(temp);
                if(res==len) {
                    ans.push_back(past_list[1]);
                    past=false;
                }
                else if(res==len+1) {
                    ans.push_back(past_list[0]);
                    ans.push_back(ar[2]); i++;
                    past=false;
                }
                else {
                    ans.push_back(past_list[0]);
                }
            }
        }
        else {
            if(i==N) {
                for(int j=0;j<2;j++) {
                    string temp=ans+ar[j];
                    if(press(temp)==N) return temp;
                }
                ans.push_back(ar[2]); return ans;
            }
            string temp;
            for(int j=0;j<4;j++) {
                temp+=ans+guess_list[j];
            }
            int res=press(temp);

            if(res==len) {
                ans.push_back(ar[2]);
            }
            else if(res==len+1) {
                ans.push_back(ar[1]);
            }
            else {
                temp="";
                for(int j=0;j<2;j++) {
                    temp+=ans+guess_list[j];
                }
                int res2=press(temp);
                if(res2==len) {
                    ans+=guess_list[3]; i++;
                }
                else if(res2==len+1) {
                    ans+=guess_list[2]; i++;
                }
                else {
                    ans.push_back(ar[0]);
                    past_list.clear();
                    past_list.push_back(ar[0]);
                    past_list.push_back(ar[1]);
                    past=true;
                }
            }
        }
    }
    return ans;
}

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