oj.uz

Submission #664267

# Submission time Handle Problem Language Result Execution time Memory
664267 2022-11-27T06:58:44 Z Nursik Password (RMI18_password) C++14
50 / 100
 910 ms 556 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];
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){
            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;
            ++kektor;
            assert(kektor <= n + n);
        }
    }
    return ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 556 KB Guessed the password with 4788 queries.
2 Correct 125 ms 332 KB Guessed the password with 10281 queries.
3 Correct 126 ms 460 KB Guessed the password with 13667 queries.
4 Correct 211 ms 352 KB Guessed the password with 20689 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 76 queries.
2 Correct 1 ms 208 KB Guessed the password with 187 queries.
3 Correct 1 ms 208 KB Guessed the password with 52 queries.
4 Correct 2 ms 208 KB Guessed the password with 116 queries.
5 Correct 3 ms 208 KB Guessed the password with 181 queries.
6 Correct 2 ms 300 KB Guessed the password with 216 queries.
7 Correct 50 ms 556 KB Guessed the password with 4788 queries.
8 Correct 125 ms 332 KB Guessed the password with 10281 queries.
9 Correct 126 ms 460 KB Guessed the password with 13667 queries.
10 Correct 211 ms 352 KB Guessed the password with 20689 queries.
11 Correct 910 ms 460 KB Guessed the password with 49512 queries.
12 Correct 289 ms 460 KB Guessed the password with 19157 queries.
13 Correct 899 ms 352 KB Guessed the password with 47683 queries.
14 Correct 372 ms 352 KB Guessed the password with 26326 queries.
15 Runtime error 871 ms 464 KB Execution killed with signal 13
16 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 76 queries.
2 Correct 1 ms 208 KB Guessed the password with 187 queries.
3 Correct 1 ms 208 KB Guessed the password with 52 queries.
4 Correct 2 ms 208 KB Guessed the password with 116 queries.
5 Correct 3 ms 208 KB Guessed the password with 181 queries.
6 Correct 2 ms 300 KB Guessed the password with 216 queries.
7 Correct 50 ms 556 KB Guessed the password with 4788 queries.
8 Correct 125 ms 332 KB Guessed the password with 10281 queries.
9 Correct 126 ms 460 KB Guessed the password with 13667 queries.
10 Correct 211 ms 352 KB Guessed the password with 20689 queries.
11 Correct 910 ms 460 KB Guessed the password with 49512 queries.
12 Correct 289 ms 460 KB Guessed the password with 19157 queries.
13 Correct 899 ms 352 KB Guessed the password with 47683 queries.
14 Correct 372 ms 352 KB Guessed the password with 26326 queries.
15 Runtime error 871 ms 464 KB Execution killed with signal 13
16 Halted 0 ms 0 KB -