oj.uz

Submission #251388

# Submission time Handle Problem Language Result Execution time Memory
251388 2020-07-21T05:05:22 Z cheeheng Password (RMI18_password) C++14
50 / 100
 632 ms 504 KB 
#include <bits/stdc++.h>
using namespace std;

int query(string q);

typedef pair<int, int> ii;

int p[28] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27};
ii cnt2[28];
int cnt[28];

string guess(int n, int s){
    for(char i = 'a'; i < 'a'+s; i ++){
        string temp = "";
        for(int j = 0; j < n; j ++){
            temp += i;
        }
        cnt[i-'a'] = query(temp);
        cnt2[i-'a'] = ii(cnt[i-'a'], i-'a');
    }

    sort(cnt2, cnt2+s);
    reverse(cnt2, cnt2+s);
    for(int i = 0; i < s; i ++){
        p[cnt2[i].second] = i;
    }

    //random_shuffle(p, p+s);
    //random_shuffle(p, p+s);

    string temp = "";
    int cntMatch = 0;
    for(int i = 0; i < s; i ++){
        int indx = 0;
        int j = 0;
        while(j < cnt[p[i]]){
            string temp2 = temp;
            if(indx == 0){
                temp2 = (char)('a'+p[i]) + temp;
            }else{
                temp2 = temp2.substr(0, indx) + (char)('a'+p[i]) + temp2.substr(indx);
            }
            //printf("%d: %s %s\n", j, temp.c_str(), temp2.c_str());
            int res = query(temp2);
            if(res > cntMatch){
                temp = temp2;
                cntMatch = res;
                j ++;
            }
            indx ++;
        }
    }

    return temp;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Guessed the password with 88 queries.
2 Correct 3 ms 256 KB Guessed the password with 157 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 78 queries.
2 Correct 2 ms 256 KB Guessed the password with 176 queries.
3 Correct 3 ms 256 KB Guessed the password with 171 queries.
4 Correct 3 ms 256 KB Guessed the password with 230 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 376 KB Guessed the password with 7537 queries.
2 Correct 107 ms 376 KB Guessed the password with 10292 queries.
3 Correct 152 ms 376 KB Guessed the password with 14265 queries.
4 Correct 214 ms 376 KB Guessed the password with 20707 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Guessed the password with 88 queries.
2 Correct 3 ms 256 KB Guessed the password with 157 queries.
3 Correct 1 ms 256 KB Guessed the password with 78 queries.
4 Correct 2 ms 256 KB Guessed the password with 176 queries.
5 Correct 3 ms 256 KB Guessed the password with 171 queries.
6 Correct 3 ms 256 KB Guessed the password with 230 queries.
7 Correct 79 ms 376 KB Guessed the password with 7537 queries.
8 Correct 107 ms 376 KB Guessed the password with 10292 queries.
9 Correct 152 ms 376 KB Guessed the password with 14265 queries.
10 Correct 214 ms 376 KB Guessed the password with 20707 queries.
11 Incorrect 632 ms 504 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Guessed the password with 88 queries.
2 Correct 3 ms 256 KB Guessed the password with 157 queries.
3 Correct 1 ms 256 KB Guessed the password with 78 queries.
4 Correct 2 ms 256 KB Guessed the password with 176 queries.
5 Correct 3 ms 256 KB Guessed the password with 171 queries.
6 Correct 3 ms 256 KB Guessed the password with 230 queries.
7 Correct 79 ms 376 KB Guessed the password with 7537 queries.
8 Correct 107 ms 376 KB Guessed the password with 10292 queries.
9 Correct 152 ms 376 KB Guessed the password with 14265 queries.
10 Correct 214 ms 376 KB Guessed the password with 20707 queries.
11 Incorrect 632 ms 504 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -