oj.uz

Submission #251387

# Submission time Handle Problem Language Result Execution time Memory
251387 2020-07-21T05:04:17 Z cheeheng Password (RMI18_password) C++14
80 / 100
 537 ms 524 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 77 queries.
2 Correct 3 ms 256 KB Guessed the password with 188 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 72 queries.
2 Correct 2 ms 256 KB Guessed the password with 150 queries.
3 Correct 2 ms 256 KB Guessed the password with 93 queries.
4 Correct 4 ms 256 KB Guessed the password with 239 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 376 KB Guessed the password with 4989 queries.
2 Correct 131 ms 376 KB Guessed the password with 10106 queries.
3 Correct 138 ms 504 KB Guessed the password with 15141 queries.
4 Correct 258 ms 376 KB Guessed the password with 19274 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Guessed the password with 77 queries.
2 Correct 3 ms 256 KB Guessed the password with 188 queries.
3 Correct 1 ms 256 KB Guessed the password with 72 queries.
4 Correct 2 ms 256 KB Guessed the password with 150 queries.
5 Correct 2 ms 256 KB Guessed the password with 93 queries.
6 Correct 4 ms 256 KB Guessed the password with 239 queries.
7 Correct 50 ms 376 KB Guessed the password with 4989 queries.
8 Correct 131 ms 376 KB Guessed the password with 10106 queries.
9 Correct 138 ms 504 KB Guessed the password with 15141 queries.
10 Correct 258 ms 376 KB Guessed the password with 19274 queries.
11 Correct 473 ms 504 KB Guessed the password with 39665 queries.
12 Correct 110 ms 380 KB Guessed the password with 10954 queries.
13 Correct 341 ms 504 KB Guessed the password with 35745 queries.
14 Correct 268 ms 504 KB Guessed the password with 22576 queries.
15 Correct 448 ms 384 KB Guessed the password with 39611 queries.
16 Correct 212 ms 504 KB Guessed the password with 17364 queries.
17 Correct 341 ms 388 KB Guessed the password with 34117 queries.
18 Correct 139 ms 504 KB Guessed the password with 13637 queries.
19 Correct 479 ms 384 KB Guessed the password with 41893 queries.
20 Correct 150 ms 504 KB Guessed the password with 13609 queries.
21 Correct 415 ms 376 KB Guessed the password with 37010 queries.
22 Correct 166 ms 508 KB Guessed the password with 15808 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Guessed the password with 77 queries.
2 Correct 3 ms 256 KB Guessed the password with 188 queries.
3 Correct 1 ms 256 KB Guessed the password with 72 queries.
4 Correct 2 ms 256 KB Guessed the password with 150 queries.
5 Correct 2 ms 256 KB Guessed the password with 93 queries.
6 Correct 4 ms 256 KB Guessed the password with 239 queries.
7 Correct 50 ms 376 KB Guessed the password with 4989 queries.
8 Correct 131 ms 376 KB Guessed the password with 10106 queries.
9 Correct 138 ms 504 KB Guessed the password with 15141 queries.
10 Correct 258 ms 376 KB Guessed the password with 19274 queries.
11 Correct 473 ms 504 KB Guessed the password with 39665 queries.
12 Correct 110 ms 380 KB Guessed the password with 10954 queries.
13 Correct 341 ms 504 KB Guessed the password with 35745 queries.
14 Correct 268 ms 504 KB Guessed the password with 22576 queries.
15 Correct 448 ms 384 KB Guessed the password with 39611 queries.
16 Correct 212 ms 504 KB Guessed the password with 17364 queries.
17 Correct 341 ms 388 KB Guessed the password with 34117 queries.
18 Correct 139 ms 504 KB Guessed the password with 13637 queries.
19 Correct 479 ms 384 KB Guessed the password with 41893 queries.
20 Correct 150 ms 504 KB Guessed the password with 13609 queries.
21 Correct 415 ms 376 KB Guessed the password with 37010 queries.
22 Correct 166 ms 508 KB Guessed the password with 15808 queries.
23 Incorrect 537 ms 524 KB Could not guess the password with 50000 queries.
24 Halted 0 ms 0 KB -