oj.uz

Submission #709226

# Submission time Handle Problem Language Result Execution time Memory
709226 2023-03-13T08:48:45 Z ecxx Password (RMI18_password) C++17
80 / 100
 468 ms 596 KB 
#include <bits/stdc++.h>
using namespace std;

#define ii pair<int, int>
#define startguess glen = 0
#define putguess(x) newguess[glen++] = x

int query(string str);

int q6(string str) {
    int res = query(str);
    //cout << "QUERY ON " << str << " : " << res << "\n";
    return res;
}

string st1(int n, int s) {

    // subtask one

    int exists[26] = { 0 };
    vector<ii> gthan(s, {0, 0});
    for (int i = 0; i < s; i++) gthan[i].second = i;

    char q[3] = "\0\0";


    for (int i = 0 ; i < s; i++) {
        q[0] = i + 'a';
        exists[i] = query(string(q));
    }


    for (int i = 0 ; i < s; i++) for (int j = i+1; j < s; j++) {
        if ((!exists[i]) || (!exists[j])) continue;
        q[0] = i + 'a';
        q[1] = j + 'a';
        int result = query(string(q));
        gthan[j].first += (result-1);
        gthan[i].first += (2-result);
    }  

    sort(gthan.begin(), gthan.end());

    string ans;
    for (auto q : gthan) {
        if (exists[q.second]) ans.push_back((char)(q.second + 'a'));
    }

    return ans;

}

string st3 (int n, int s) {

    int glen, guesslength;

    char buf[n+2];
    memset(buf, 0, n+2);

    char guess[n+2];
    memset(guess, 0, n+2);

    char newguess[n+2];
    memset(guess, 0, n+2);

   vector<pair<int,int> > numletter(s, {0, 0});

    for (int i = 0; i < s; i++) {
        memset(buf, i+'a', n);
        numletter[i] = {query(string(buf)), i};
    }

    sort(numletter.begin(), numletter.end());

    memset(buf, 0, n+2);
    memset(guess, 'a'+numletter[0].second, numletter[0].first);

    for (int iv = 0; iv < s-1; iv++) {

        int nltr = numletter[iv+1].second;

        //cout << guess << " " << strlen(guess) << "\n";

        memset(buf, nltr+'a', n);

        startguess;

        int nonc = numletter[iv+1].first;
        //cout << "IN TOTAL THERE ARE " << nonc << " OF " << (char)(nltr+'a') << "\n";
        for (int j = 0; j < strlen(guess); j++) {
            buf[j] = guess[j];
            int nnonc = nonc - (q6(string(buf)) - (j+1));
            //cout << "PUTTING " << nnonc << " OF " << (char)(nltr+'a') << "\n";
            for (int qqqq = 0; qqqq < nnonc; qqqq++) { 
                putguess(nltr+'a'); 
            }
            putguess(buf[j]);
            nonc -= nnonc;
        }
        for (int qqqq = 0; qqqq < nonc; qqqq++) putguess(nltr+'a');

        //cout << "IN TOTAL THERE ARE " << nonc << " OF " << (nltr+'a') << "\n\n";

        for (int z = 0; z < glen; z++) {
            guess[z] = newguess[z];
        }

    }

    return string(guess);

}

string guess (int n, int s) {
    return st3 (n, s);
}

Compilation message

password.cpp: In function 'std::string st3(int, int)':
password.cpp:90:27: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for (int j = 0; j < strlen(guess); j++) {
      |                         ~~^~~~~~~~~~~~~~~
password.cpp:55:15: warning: unused variable 'guesslength' [-Wunused-variable]
   55 |     int glen, guesslength;
      |               ^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 121 queries.
2 Correct 4 ms 208 KB Guessed the password with 277 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 27 queries.
2 Correct 1 ms 208 KB Guessed the password with 32 queries.
3 Correct 1 ms 208 KB Guessed the password with 18 queries.
4 Correct 1 ms 208 KB Guessed the password with 90 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 208 KB Guessed the password with 2149 queries.
2 Correct 68 ms 208 KB Guessed the password with 8435 queries.
3 Correct 38 ms 208 KB Guessed the password with 3621 queries.
4 Correct 119 ms 208 KB Guessed the password with 12042 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 121 queries.
2 Correct 4 ms 208 KB Guessed the password with 277 queries.
3 Correct 1 ms 208 KB Guessed the password with 27 queries.
4 Correct 1 ms 208 KB Guessed the password with 32 queries.
5 Correct 1 ms 208 KB Guessed the password with 18 queries.
6 Correct 1 ms 208 KB Guessed the password with 90 queries.
7 Correct 23 ms 208 KB Guessed the password with 2149 queries.
8 Correct 68 ms 208 KB Guessed the password with 8435 queries.
9 Correct 38 ms 208 KB Guessed the password with 3621 queries.
10 Correct 119 ms 208 KB Guessed the password with 12042 queries.
11 Correct 61 ms 208 KB Guessed the password with 6623 queries.
12 Correct 50 ms 208 KB Guessed the password with 6656 queries.
13 Correct 147 ms 208 KB Guessed the password with 14982 queries.
14 Correct 161 ms 208 KB Guessed the password with 15360 queries.
15 Correct 113 ms 208 KB Guessed the password with 11294 queries.
16 Correct 111 ms 208 KB Guessed the password with 11198 queries.
17 Correct 95 ms 312 KB Guessed the password with 8953 queries.
18 Correct 70 ms 304 KB Guessed the password with 9035 queries.
19 Correct 91 ms 308 KB Guessed the password with 7612 queries.
20 Correct 95 ms 208 KB Guessed the password with 7835 queries.
21 Correct 92 ms 312 KB Guessed the password with 11804 queries.
22 Correct 107 ms 312 KB Guessed the password with 11922 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 121 queries.
2 Correct 4 ms 208 KB Guessed the password with 277 queries.
3 Correct 1 ms 208 KB Guessed the password with 27 queries.
4 Correct 1 ms 208 KB Guessed the password with 32 queries.
5 Correct 1 ms 208 KB Guessed the password with 18 queries.
6 Correct 1 ms 208 KB Guessed the password with 90 queries.
7 Correct 23 ms 208 KB Guessed the password with 2149 queries.
8 Correct 68 ms 208 KB Guessed the password with 8435 queries.
9 Correct 38 ms 208 KB Guessed the password with 3621 queries.
10 Correct 119 ms 208 KB Guessed the password with 12042 queries.
11 Correct 61 ms 208 KB Guessed the password with 6623 queries.
12 Correct 50 ms 208 KB Guessed the password with 6656 queries.
13 Correct 147 ms 208 KB Guessed the password with 14982 queries.
14 Correct 161 ms 208 KB Guessed the password with 15360 queries.
15 Correct 113 ms 208 KB Guessed the password with 11294 queries.
16 Correct 111 ms 208 KB Guessed the password with 11198 queries.
17 Correct 95 ms 312 KB Guessed the password with 8953 queries.
18 Correct 70 ms 304 KB Guessed the password with 9035 queries.
19 Correct 91 ms 308 KB Guessed the password with 7612 queries.
20 Correct 95 ms 208 KB Guessed the password with 7835 queries.
21 Correct 92 ms 312 KB Guessed the password with 11804 queries.
22 Correct 107 ms 312 KB Guessed the password with 11922 queries.
23 Execution timed out 468 ms 596 KB Time limit exceeded (wall clock)
24 Halted 0 ms 0 KB -