oj.uz

Submission #709416

# Submission time Handle Problem Language Result Execution time Memory
709416 2023-03-13T14:18:13 Z salmon Password (RMI18_password) C++17
0 / 100
 5 ms 300 KB 
#include <bits/stdc++.h>
using namespace std;

int query(string str);

string guess(int N, int S){
    int t = 0;

    struct node{
        int v;
        node *l,*r;

        node(int s){
            v = s;
            l = NULL;
            r = NULL;
        }

    }*aas,*infront,*inback;

    aas = new node(0);

    string alphabet = "";

    for(int i = 'a'; i < 'a' + S; i++){
        alphabet.push_back(i);
    }

    inback = aas -> r;
    infront = aas;

    for(int i = 1; i <= N - 30; i++){
        string temp = "";
        string temp1 = "";

        node *point = aas;
        while(point != inback){
            if(point -> v == 0){
                point = point -> r;
            }
            else{
                temp.push_back(point -> v);
                point = point -> r;
            }
        }

        point = inback;
        while(point != NULL){
            if(point -> v == 0){
                point = point -> r;
            }
            else{
                temp1.push_back(point -> v);
                point = point -> r;
            }
        }

        if(query(temp + alphabet + temp1) < i){
            inback = infront;
            infront = infront -> l;
            i--;
            continue;
        }

        int s = 'a';
        int e = 'a' + S - 1;

        while(s != e){
            int m = (s + e)/2;

            string temp2 = temp;

            for(int i = s; i <= m; i++){
                temp2.push_back(s);
            }

            temp2 = temp2 + temp1;

            if(query(temp2) >= i){
                e = m;
            }
            else{
                s = m + 1;
            }
        }

        node *temp3 = new node(s);
        infront -> r = temp3;
        temp3 -> l = infront;
        infront = temp3;
        inback = temp3 -> r;
    }

    for(int i = max(1,N - 29); i <= N; i++){
        string temp = "";
        string temp1 = "";

        node *point;
        point = aas;
        while(point != inback){
            if(point -> v == 0){
                point = point -> r;
            }
            else{
                temp.push_back(point -> v);
                point = point -> r;
            }
        }

        point = inback;
        while(point != NULL){
            if(point -> v == 0){
                point = point -> r;
            }
            else{
                temp1.push_back(point -> v);
                point = point -> r;
            }
        }
       // cout << "s" + temp + " " + temp1 << endl;

        int s = 'a';
        int e = 'a' + S - 1;
        string temp2;

        for(char j = s; j <= e; j++){
            temp2 = temp;
            temp2.push_back(j);
            temp2 = temp2 + temp1;
            //cout << temp2 << endl;
            if(query(temp2) == i){
                    //cout << "j = " << j  << endl;
                node *temp3 = new node(j);
                infront -> r = temp3;
                temp3 -> l = infront;
                infront = temp3;
                temp3 -> r = inback;
                temp = temp2;
                break;
            }
        }

        if(query(temp) < i){
            inback = infront;
            infront = infront -> l;
            i--;
            continue;
        }
    }

    string temp = "";
    string temp1 = "";

    node *point = aas;
    while(point != NULL){
        if(point -> v == 0){
            point = point -> r;
        }
        else{
            temp1.push_back(point -> v);
            point = point -> r;
        }
    }

    return temp + temp1;

}
/*
26 26 lmopqrstuvwnabcdefghjikxyz
*/

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:7:9: warning: unused variable 't' [-Wunused-variable]
    7 |     int t = 0;
      |         ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 208 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 208 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 300 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 208 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 208 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -