Submission #995554

#	Time	Username	Problem	Language	Result	Execution time	Memory
995554		amine_aroua	Password (RMI18_password)	C++17	100 / 100	219 ms	6716 KiB

password

#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define pb push_back
#define nl '\n'
#define fore(i, y) for(int i = 0; i < y; i++)
#define forr(i, x, y) for(int i = x;i<=y;i++)
#define forn(i, y, x) for(int i = y; i >= x; i--)
using namespace std;
int query(string q) ;
string comb(string a , string b)
{
    if(b.empty())
        return a;
    if(a.empty())
        return b;
    string cur = "";
    vector<string> suf;
    forn(i , (int)b.size() - 1 , 0)
    {
        cur+=b[i];
        string rcur = cur;
        reverse(rcur.begin() , rcur.end());
        suf.pb(rcur);
    }
    reverse(suf.begin() , suf.end());
    suf.pb("");
    string res = "";
    int ptr = 0;
    forr(i , 0 , (int)b.size())
    {
        if(ptr == (int)a.size())
        {
            if(i < (int)b.size())
                res+=b[i];
            continue;
        }
        string beg = "";
        beg+=a[ptr];
        string new_res = res + beg + suf[i];
        while(query(new_res) == (int)new_res.size())
        {
            res = res + beg;
            ptr++;
            if(ptr == (int)a.size())
                break;
            beg = "";
            beg+=a[ptr];
            new_res = res + beg + suf[i];
        }
        if(i < (int)b.size())
            res+=b[i];
    }
    return res;
}
string get(int l , int r , int &N)
{
    if(l == r)
    {
        string str = string(N , (char)('a' + l));
        int L = query(str);
        return string(L , (char)('a' + l));
    }
    int mid = (l + r)/2;
    string a = get(l , mid , N) , b = get(mid + 1 , r , N);
    return comb(a , b);
}
string guess(int N, int S)
{
    return get(0 , S - 1 , N);
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 30 / 30
• Subtask 5: 20 / 20