Submission #81138

#	Time	Username	Problem	Language	Result	Execution time	Memory
81138		cki86201	Combo (IOI18_combo)	C++11	100 / 100	45 ms	588 KiB

combo

#include "combo.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

char change(int x) { return "ABXY"[x]; }
int p[3];

int query(string &now, vector <int> a) {
    string t = "";
    for(int e : a) {
        t = t + now;
        t.pb(change(p[e / 3]));
        t.pb(change(p[e % 3]));
    }
    return press(t);
}

std::string guess_sequence(int N) {
    int t = press("AB");
    int st = -1;
    if(t >= 1) {
        if(press("A")) st = 0;
        else st = 1;
    }
    else {
        if(press("X")) st = 2;
        else st = 3;
    }
    string now; now.pb(change(st));
    int pz = 0;
    for(int i=0;i<4;i++) if(i != st) p[pz++] = i;
    for(int i=2;i<=N;) {
        if(i+1 <= N) {
            int q1 = query(now, {1, 2, 5});
            if(q1 == szz(now)) {
                now.pb(change(p[2]));
                i += 1;
            }
            else if(q1 == szz(now) + 2) {
                int q2 = query(now, {1}) - szz(now);
                if(q2 == 2) { now.pb(change(p[0])); now.pb(change(p[1])); }
                else if(q2 == 1) { now.pb(change(p[0])); now.pb(change(p[2])); }
                else { now.pb(change(p[1])); now.pb(change(p[2])); }
                i += 2;
            }
            else {
                int q2 = query(now, {3}) - szz(now);
                if(q2 == 2) { now.pb(change(p[1])); now.pb(change(p[0])); }
                else if(q2 == 1) { now.pb(change(p[1])); now.pb(change(p[1])); }
                else { now.pb(change(p[0])); now.pb(change(p[0])); }
                i += 2;
            }
        }
        else {
            string tnow = now;
            tnow.pb(change(p[0]));
            if(press(tnow) == N) now = tnow;
            else {
                tnow.pop_back();
                tnow.pb(change(p[1]));
                if(press(tnow) == N) now = tnow;
                else {
                    tnow.pop_back();
                    tnow.pb(change(p[2]));
                    now = tnow;
                }
            }
            i += 1;
        }
    }
    return now;
}

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