oj.uz

Submission #709208

# Submission time Handle Problem Language Result Execution time Memory
709208 2023-03-13T08:20:06 Z beepbeepsheep Password (RMI18_password) C++17
50 / 100
 1706 ms 118056 KB 
    #include <bits/stdc++.h>
    using namespace std;
    int arr[26];
    int query(string s);
    string build(string s, char c, int pos){
        string ret="";
        for (int i=0;i<pos;i++){
            ret+=s[i];
        }
        ret+=c;
        for (int i=pos;i<s.size();i++){
            ret+=s[i];
        }
        return ret;
    }
    string mrg(string a, string b){
        if (a.size()>b.size()) swap(a,b);
        if (a=="") return b;
        string ans=b;
        int l=0,r=ans.size()+1,m;
        for (int i=0;i<a.size();i++){
            for (int m=l;m<=ans.size()+1;m++){
                string test=build(ans,a[i],m);
                int res=query(test);
                if (res==test.length()){
                    l=m;
                    ans=build(ans,a[i],m);
                    break;
            }
            cerr<<ans<<endl;
        }
    }
    return ans;
    }
    string dup(char c, int n){
        string ret="";
        for (int i=0;i<n;i++) ret+=c;
        return ret;
    }
    string guess(int n, int s){
        for (int i=0;i<s;i++){
            arr[i]=query(dup(i+'a',n));
        }
        string ans="";
        for (int i=0;i<s;i++){
            ans=mrg(ans,dup(i+'a',arr[i]));
        }
        return ans;
    }

Compilation message

password.cpp: In function 'std::string build(std::string, char, int)':
password.cpp:11:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |         for (int i=pos;i<s.size();i++){
      |                        ~^~~~~~~~~
password.cpp: In function 'std::string mrg(std::string, std::string)':
password.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for (int i=0;i<a.size();i++){
      |                      ~^~~~~~~~~
password.cpp:22:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |             for (int m=l;m<=ans.size()+1;m++){
      |                          ~^~~~~~~~~~~~~~
password.cpp:25:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |                 if (res==test.length()){
      |                     ~~~^~~~~~~~~~~~~~~
password.cpp:20:17: warning: unused variable 'r' [-Wunused-variable]
   20 |         int l=0,r=ans.size()+1,m;
      |                 ^
password.cpp:20:32: warning: unused variable 'm' [-Wunused-variable]
   20 |         int l=0,r=ans.size()+1,m;
      |                                ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 75 queries.
2 Correct 3 ms 208 KB Guessed the password with 188 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 72 queries.
2 Correct 2 ms 208 KB Guessed the password with 135 queries.
3 Correct 2 ms 208 KB Guessed the password with 115 queries.
4 Correct 5 ms 208 KB Guessed the password with 268 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 3164 KB Guessed the password with 5277 queries.
2 Correct 196 ms 9344 KB Guessed the password with 11372 queries.
3 Correct 297 ms 13292 KB Guessed the password with 13732 queries.
4 Correct 452 ms 26412 KB Guessed the password with 22278 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 75 queries.
2 Correct 3 ms 208 KB Guessed the password with 188 queries.
3 Correct 1 ms 208 KB Guessed the password with 72 queries.
4 Correct 2 ms 208 KB Guessed the password with 135 queries.
5 Correct 2 ms 208 KB Guessed the password with 115 queries.
6 Correct 5 ms 208 KB Guessed the password with 268 queries.
7 Correct 95 ms 3164 KB Guessed the password with 5277 queries.
8 Correct 196 ms 9344 KB Guessed the password with 11372 queries.
9 Correct 297 ms 13292 KB Guessed the password with 13732 queries.
10 Correct 452 ms 26412 KB Guessed the password with 22278 queries.
11 Execution timed out 1706 ms 118056 KB Time limit exceeded (wall clock)
12 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 75 queries.
2 Correct 3 ms 208 KB Guessed the password with 188 queries.
3 Correct 1 ms 208 KB Guessed the password with 72 queries.
4 Correct 2 ms 208 KB Guessed the password with 135 queries.
5 Correct 2 ms 208 KB Guessed the password with 115 queries.
6 Correct 5 ms 208 KB Guessed the password with 268 queries.
7 Correct 95 ms 3164 KB Guessed the password with 5277 queries.
8 Correct 196 ms 9344 KB Guessed the password with 11372 queries.
9 Correct 297 ms 13292 KB Guessed the password with 13732 queries.
10 Correct 452 ms 26412 KB Guessed the password with 22278 queries.
11 Execution timed out 1706 ms 118056 KB Time limit exceeded (wall clock)
12 Halted 0 ms 0 KB -