oj.uz

Submission #664244

# Submission time Handle Problem Language Result Execution time Memory
664244 2022-11-27T06:50:40 Z Nursik Password (RMI18_password) C++17
50 / 100
 1137 ms 784 KB 
#include <stdio.h>
 
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

#define ll long long
#define pb push_back


int is[30];
string lst[10000];
int query(string str);
string guess(int n, int s){
    string ans = "";
    int mx = 0, c = -1;
    for (int i = 0; i < s; ++i){
        string lol = "";
        char ch = 'a';
        ch += i;
        for (int j = 1; j <= n; ++j){
            lol += ch;
        }
        int kek = query(lol);
        if (kek > mx){
            mx = kek;
            c = i;
        }
        is[i] = kek;
    }
    for (int j = 1; j <= mx; ++j){
        char ch = 'a';
        ch += c;
        ans += ch;
    }
    is[c] = 0;
    for (int i = 0; i < s; ++i){
        if (is[i] == 0){
            continue;
        }
        int kektor = 0;
        while (is[i] > 0){
            ++kektor;
            char ch = 'a';
            ch += i;
            int len = (int)ans.size();
            int len2 = len;
            string nans = "", pref = "";
            for (int j = 0; j <= len; ++j){
                string suff = "";
                for (int k = j; k < len; ++k){
                    suff += ans[k];
                }
                while (is[i] > 0){
                    string q = nans;
                    q += ch;
                    q += suff;
                    if ((int)q.size() > n)
                        break;
                    int kek = query(q);
                    if (kek == len2 + 1){
                        nans += ch;
                        is[i] -= 1;
                        len2 += 1;
                    }
                    else{
                        break;
                    }
                }
                if (j < len){
                    nans += ans[j];
                    pref += ans[j];
                }
            }
            ans = nans;
        }
    }
    return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Guessed the password with 76 queries.
2 Correct 2 ms 592 KB Guessed the password with 187 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Guessed the password with 52 queries.
2 Correct 2 ms 592 KB Guessed the password with 116 queries.
3 Correct 4 ms 592 KB Guessed the password with 181 queries.
4 Correct 3 ms 592 KB Guessed the password with 216 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 644 KB Guessed the password with 4788 queries.
2 Correct 127 ms 652 KB Guessed the password with 10281 queries.
3 Correct 158 ms 652 KB Guessed the password with 13667 queries.
4 Correct 255 ms 660 KB Guessed the password with 20689 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Guessed the password with 76 queries.
2 Correct 2 ms 592 KB Guessed the password with 187 queries.
3 Correct 1 ms 592 KB Guessed the password with 52 queries.
4 Correct 2 ms 592 KB Guessed the password with 116 queries.
5 Correct 4 ms 592 KB Guessed the password with 181 queries.
6 Correct 3 ms 592 KB Guessed the password with 216 queries.
7 Correct 50 ms 644 KB Guessed the password with 4788 queries.
8 Correct 127 ms 652 KB Guessed the password with 10281 queries.
9 Correct 158 ms 652 KB Guessed the password with 13667 queries.
10 Correct 255 ms 660 KB Guessed the password with 20689 queries.
11 Correct 881 ms 664 KB Guessed the password with 49512 queries.
12 Correct 273 ms 780 KB Guessed the password with 19157 queries.
13 Correct 815 ms 660 KB Guessed the password with 47683 queries.
14 Correct 358 ms 644 KB Guessed the password with 26326 queries.
15 Correct 855 ms 752 KB Guessed the password with 44836 queries.
16 Correct 348 ms 664 KB Guessed the password with 24336 queries.
17 Runtime error 1137 ms 784 KB Execution killed with signal 13
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Guessed the password with 76 queries.
2 Correct 2 ms 592 KB Guessed the password with 187 queries.
3 Correct 1 ms 592 KB Guessed the password with 52 queries.
4 Correct 2 ms 592 KB Guessed the password with 116 queries.
5 Correct 4 ms 592 KB Guessed the password with 181 queries.
6 Correct 3 ms 592 KB Guessed the password with 216 queries.
7 Correct 50 ms 644 KB Guessed the password with 4788 queries.
8 Correct 127 ms 652 KB Guessed the password with 10281 queries.
9 Correct 158 ms 652 KB Guessed the password with 13667 queries.
10 Correct 255 ms 660 KB Guessed the password with 20689 queries.
11 Correct 881 ms 664 KB Guessed the password with 49512 queries.
12 Correct 273 ms 780 KB Guessed the password with 19157 queries.
13 Correct 815 ms 660 KB Guessed the password with 47683 queries.
14 Correct 358 ms 644 KB Guessed the password with 26326 queries.
15 Correct 855 ms 752 KB Guessed the password with 44836 queries.
16 Correct 348 ms 664 KB Guessed the password with 24336 queries.
17 Runtime error 1137 ms 784 KB Execution killed with signal 13
18 Halted 0 ms 0 KB -