oj.uz

Submission #476088

# Submission time Handle Problem Language Result Execution time Memory
476088 2021-09-24T18:15:04 Z stefantaga Password (RMI18_password) C++14
30 / 100
 522 ms 300 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 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++)
    {
        ceau[i]=i;
    }
    sort (ceau+1,ceau+s+1,compare);
    for (int t=1;t<=s;t++)
    {
        i=ceau[t];
        string acum;
        pozitie=0;
        for (j=1;j<=s;j++)
        {
            inainte[j]=0;
        }
        for (poz=1;poz<=fr[i];poz++)
        {
            for (j=1;j<=s;j++)
            {
                if (j==i)
                {
                    continue;
                }
                st=1;
                dr=fr[j]-inainte[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;
                    }
                }
                inainte[j]+=sol;
                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 4 ms 200 KB Guessed the password with 271 queries.
2 Correct 9 ms 200 KB Guessed the password with 622 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Guessed the password with 167 queries.
2 Correct 5 ms 200 KB Guessed the password with 367 queries.
3 Correct 4 ms 200 KB Guessed the password with 361 queries.
4 Correct 9 ms 300 KB Guessed the password with 893 queries.

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 300 KB Guessed the password with 35158 queries.
2 Incorrect 522 ms 300 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 4 ms 200 KB Guessed the password with 271 queries.
2 Correct 9 ms 200 KB Guessed the password with 622 queries.
3 Correct 2 ms 200 KB Guessed the password with 167 queries.
4 Correct 5 ms 200 KB Guessed the password with 367 queries.
5 Correct 4 ms 200 KB Guessed the password with 361 queries.
6 Correct 9 ms 300 KB Guessed the password with 893 queries.
7 Correct 427 ms 300 KB Guessed the password with 35158 queries.
8 Incorrect 522 ms 300 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 4 ms 200 KB Guessed the password with 271 queries.
2 Correct 9 ms 200 KB Guessed the password with 622 queries.
3 Correct 2 ms 200 KB Guessed the password with 167 queries.
4 Correct 5 ms 200 KB Guessed the password with 367 queries.
5 Correct 4 ms 200 KB Guessed the password with 361 queries.
6 Correct 9 ms 300 KB Guessed the password with 893 queries.
7 Correct 427 ms 300 KB Guessed the password with 35158 queries.
8 Incorrect 522 ms 300 KB Could not guess the password with 50000 queries.
9 Halted 0 ms 0 KB -