oj.uz

Submission #476097

# Submission time Handle Problem Language Result Execution time Memory
476097 2021-09-24T18:46:14 Z stefantaga Password (RMI18_password) C++14
100 / 100
 251 ms 608 KB 
#include <bits/stdc++.h>
#include <fstream>
#include <iostream>
#include <sstream>
#include <string>
#include <stdlib.h>
#include <assert.h>

using namespace std;

int query(string str);
string sol,acum;
int n,s;
char litera[105];
bool intreaba(char litera,int x)
{
    string acum;
    for (int i=1;i<=x;i++)
    {
        acum.push_back(litera);
    }
    if (query(acum)==x)
    {
        return 1;
    }
    return 0;
}
int fr[105],poz,pozitie,inainte[1005],ceau[5005];
char finalsol[5005];
bool compare (int a,int b)
{
    return fr[a]>fr[b];
}
string divide(int st,int dr)
{
    if (st==dr)
    {
        string acum;
        for (int i=1;i<=fr[st];i++)
        {
            acum.push_back(litera[st]);
        }
        return acum;
    }
    int mij=(st+dr)/2;
    string stanga=divide(st,mij);
    string dreapta=divide(mij+1,dr);
    string panaacum;
    while (stanga.size()&&dreapta.size())
    {
        string ceintreb = panaacum+stanga[0]+dreapta;
        if (query(ceintreb)==ceintreb.size())
        {
            panaacum+=stanga[0];
            stanga.erase(stanga.begin());
        }
        else
        {
            panaacum+=dreapta[0];
            dreapta.erase(dreapta.begin());
        }
    }
    panaacum+=stanga;
    panaacum+=dreapta;
    return panaacum;
}
string guess (int N,int S)
{
    int i,st,dr,mij,sol,j,k;
    n=N;s=S;
    for (i=1;i<=s;i++)
    {
        litera[i]=(char(i+96));
        st=1;
        dr=n;
        sol=0;
        while (st<=dr)
        {
            mij=(st+dr)/2;
            if (intreaba(litera[i],mij)==1)
            {
                sol=mij;
                st=mij+1;
            }
            else
            {
                dr=mij-1;
            }
        }
        fr[i]=sol;
    }
    string salut=divide(1,s);
    return salut;
}

Compilation message

password.cpp: In function 'std::string divide(int, int)':
password.cpp:52:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         if (query(ceintreb)==ceintreb.size())
      |             ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
password.cpp: In function 'std::string guess(int, int)':
password.cpp:69:25: warning: unused variable 'j' [-Wunused-variable]
   69 |     int i,st,dr,mij,sol,j,k;
      |                         ^
password.cpp:69:27: warning: unused variable 'k' [-Wunused-variable]
   69 |     int i,st,dr,mij,sol,j,k;
      |                           ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Guessed the password with 106 queries.
2 Correct 2 ms 200 KB Guessed the password with 193 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Guessed the password with 59 queries.
2 Correct 2 ms 200 KB Guessed the password with 133 queries.
3 Correct 2 ms 200 KB Guessed the password with 109 queries.
4 Correct 3 ms 200 KB Guessed the password with 221 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 320 KB Guessed the password with 3564 queries.
2 Correct 58 ms 316 KB Guessed the password with 5169 queries.
3 Correct 72 ms 428 KB Guessed the password with 6531 queries.
4 Correct 96 ms 320 KB Guessed the password with 8892 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Guessed the password with 106 queries.
2 Correct 2 ms 200 KB Guessed the password with 193 queries.
3 Correct 1 ms 200 KB Guessed the password with 59 queries.
4 Correct 2 ms 200 KB Guessed the password with 133 queries.
5 Correct 2 ms 200 KB Guessed the password with 109 queries.
6 Correct 3 ms 200 KB Guessed the password with 221 queries.
7 Correct 42 ms 320 KB Guessed the password with 3564 queries.
8 Correct 58 ms 316 KB Guessed the password with 5169 queries.
9 Correct 72 ms 428 KB Guessed the password with 6531 queries.
10 Correct 96 ms 320 KB Guessed the password with 8892 queries.
11 Correct 111 ms 344 KB Guessed the password with 13905 queries.
12 Correct 133 ms 348 KB Guessed the password with 12725 queries.
13 Correct 140 ms 424 KB Guessed the password with 14667 queries.
14 Correct 145 ms 336 KB Guessed the password with 14215 queries.
15 Correct 121 ms 428 KB Guessed the password with 15354 queries.
16 Correct 155 ms 452 KB Guessed the password with 14435 queries.
17 Correct 171 ms 468 KB Guessed the password with 16337 queries.
18 Correct 148 ms 468 KB Guessed the password with 15473 queries.
19 Correct 177 ms 452 KB Guessed the password with 16696 queries.
20 Correct 165 ms 432 KB Guessed the password with 14532 queries.
21 Correct 208 ms 320 KB Guessed the password with 17131 queries.
22 Correct 158 ms 444 KB Guessed the password with 15598 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Guessed the password with 106 queries.
2 Correct 2 ms 200 KB Guessed the password with 193 queries.
3 Correct 1 ms 200 KB Guessed the password with 59 queries.
4 Correct 2 ms 200 KB Guessed the password with 133 queries.
5 Correct 2 ms 200 KB Guessed the password with 109 queries.
6 Correct 3 ms 200 KB Guessed the password with 221 queries.
7 Correct 42 ms 320 KB Guessed the password with 3564 queries.
8 Correct 58 ms 316 KB Guessed the password with 5169 queries.
9 Correct 72 ms 428 KB Guessed the password with 6531 queries.
10 Correct 96 ms 320 KB Guessed the password with 8892 queries.
11 Correct 111 ms 344 KB Guessed the password with 13905 queries.
12 Correct 133 ms 348 KB Guessed the password with 12725 queries.
13 Correct 140 ms 424 KB Guessed the password with 14667 queries.
14 Correct 145 ms 336 KB Guessed the password with 14215 queries.
15 Correct 121 ms 428 KB Guessed the password with 15354 queries.
16 Correct 155 ms 452 KB Guessed the password with 14435 queries.
17 Correct 171 ms 468 KB Guessed the password with 16337 queries.
18 Correct 148 ms 468 KB Guessed the password with 15473 queries.
19 Correct 177 ms 452 KB Guessed the password with 16696 queries.
20 Correct 165 ms 432 KB Guessed the password with 14532 queries.
21 Correct 208 ms 320 KB Guessed the password with 17131 queries.
22 Correct 158 ms 444 KB Guessed the password with 15598 queries.
23 Correct 184 ms 500 KB Guessed the password with 23904 queries.
24 Correct 240 ms 420 KB Guessed the password with 22525 queries.
25 Correct 251 ms 576 KB Guessed the password with 24088 queries.
26 Correct 211 ms 496 KB Guessed the password with 23623 queries.
27 Correct 198 ms 568 KB Guessed the password with 24055 queries.
28 Correct 228 ms 608 KB Guessed the password with 23338 queries.
29 Correct 220 ms 584 KB Guessed the password with 24140 queries.
30 Correct 246 ms 600 KB Guessed the password with 22795 queries.