Submission #528649

#	Time	Username	Problem	Language	Result	Execution time	Memory
528649		rayfish	Combo (IOI18_combo)	C++17	100 / 100	28 ms	568 KiB

combo

/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/IOI18_combo
*/
#include <iostream>  //cin , cout
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>
#include <string.h>
#include <set>

using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define ff  first
#define ss  second
#define pb  push_back
#define sz(x)   (int)(x).size()

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e5+5;   //
const ll  INF = 1e18;    //

#define MAXV 300007
#define MAXE 100007


bool debug= false;

/*
int press(string s) {
}*/

#include "combo.h"
string guess_sequence(int N) {
    string s = "";
    vector<string> b = {"A", "B", "X", "Y"};

    // find the starting char first
    if(press(b[0]+b[1])>0) {    // AB or A
        if(press(b[0])>0) {
            // A
        } else {    //B
            swap(b[0], b[1]);
        }
    } else if(press(b[2])>0) {  // X
        swap(b[0], b[2]);
    } else {
        swap(b[0], b[3]);
    }
    s += b[0];

    // special case
    if(N==1) return s;

    // build s one by one. case: ABA = +1, AC*A = +2, or AD*A = +0
    for(int len=2;len<=N-1; len++) {
        string cmd = s+b[1] + s+b[2]+b[1] + s+b[2]+b[2] + s+b[2]+b[3];
        int p = press(cmd);
        if(p == sz(s)+1) s += b[1];
        else if(p == sz(s)+2) s += b[2];
        else s += b[3];
    }

    // last char
    if(press(s+b[1])==N) s += b[1];
    else if (press(s+b[2])==N) s += b[2];
    else s += b[3];

    return s;
}

/*
int N;

int main() {
    debug = true;
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> N;

    if(debug) cout << endl << "EOL" << endl;

}
*/

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