oj.uz

Submission #476082

# Submission time Handle Problem Language Result Execution time Memory
476082 2021-09-24T17:56:40 Z stefantaga Password (RMI18_password) C++14
30 / 100
 577 ms 412 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;
char finalsol[5005];
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;
    }
    for (i=1;i<=s;i++)
    {
        string acum;
        pozitie=0;
        for (poz=1;poz<=fr[i];poz++)
        {
            for (j=1;j<=s;j++)
            {
                if (j==i)
                {
                    continue;
                }
                st=1;
                dr=fr[j];
                sol=0;
                while (st<=dr)
                {
                    mij=(st+dr)/2;
                    string copie=acum;
                    for (k=1;k<=mij;k++)
                    {
                        copie.push_back(litera[j]);
                    }
                    for (k=1;k<=fr[i]-poz+1;k++)
                    {
                        copie.push_back(litera[i]);
                    }
                    if (query(copie)==mij+fr[i])
                    {
                        sol=mij;
                        st=mij+1;
                    }
                    else
                    {
                        dr=mij-1;
                    }
                }
                pozitie+=sol;
            }
            pozitie++;
            finalsol[pozitie]=litera[i];
            acum.push_back(litera[i]);
        }
    }
    string solfin;
    for (i=1;i<=n;i++)
    {
        solfin.push_back(finalsol[i]);
    }
    return solfin;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 200 KB Guessed the password with 271 queries.
2 Correct 8 ms 200 KB Guessed the password with 622 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 200 KB Guessed the password with 229 queries.
2 Correct 7 ms 200 KB Guessed the password with 496 queries.
3 Correct 5 ms 200 KB Guessed the password with 424 queries.
4 Correct 14 ms 200 KB Guessed the password with 1211 queries.

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 577 ms 412 KB Guessed the password with 47538 queries.
2 Incorrect 507 ms 280 KB Could not guess the password with 50000 queries.
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 200 KB Guessed the password with 271 queries.
2 Correct 8 ms 200 KB Guessed the password with 622 queries.
3 Correct 4 ms 200 KB Guessed the password with 229 queries.
4 Correct 7 ms 200 KB Guessed the password with 496 queries.
5 Correct 5 ms 200 KB Guessed the password with 424 queries.
6 Correct 14 ms 200 KB Guessed the password with 1211 queries.
7 Correct 577 ms 412 KB Guessed the password with 47538 queries.
8 Incorrect 507 ms 280 KB Could not guess the password with 50000 queries.
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 200 KB Guessed the password with 271 queries.
2 Correct 8 ms 200 KB Guessed the password with 622 queries.
3 Correct 4 ms 200 KB Guessed the password with 229 queries.
4 Correct 7 ms 200 KB Guessed the password with 496 queries.
5 Correct 5 ms 200 KB Guessed the password with 424 queries.
6 Correct 14 ms 200 KB Guessed the password with 1211 queries.
7 Correct 577 ms 412 KB Guessed the password with 47538 queries.
8 Incorrect 507 ms 280 KB Could not guess the password with 50000 queries.
9 Halted 0 ms 0 KB -