oj.uz

Submission #664206

# Submission time Handle Problem Language Result Execution time Memory
664206 2022-11-27T06:42:30 Z Nursik Password (RMI18_password) C++14
50 / 100
 864 ms 348 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;
        }
        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 add = "";
                int lol = 0;
                string suff = "";
                for (int k = j; k < len; ++k){
                    suff += ans[k];
                }
                while (1){
                    string q = nans;
                    q += ch;
                    q += suff;
                    if ((int)q.size() > n)
                        break;
                    int kek = query(q);
                    if (kek == len2 + 1){
                        lol += 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 2 ms 208 KB Guessed the password with 146 queries.
2 Correct 3 ms 208 KB Guessed the password with 315 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 52 queries.
2 Correct 3 ms 272 KB Guessed the password with 120 queries.
3 Correct 2 ms 336 KB Guessed the password with 182 queries.
4 Correct 2 ms 208 KB Guessed the password with 223 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 332 KB Guessed the password with 5477 queries.
2 Correct 145 ms 344 KB Guessed the password with 10742 queries.
3 Correct 194 ms 340 KB Guessed the password with 16434 queries.
4 Correct 285 ms 348 KB Guessed the password with 21089 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 146 queries.
2 Correct 3 ms 208 KB Guessed the password with 315 queries.
3 Correct 2 ms 208 KB Guessed the password with 52 queries.
4 Correct 3 ms 272 KB Guessed the password with 120 queries.
5 Correct 2 ms 336 KB Guessed the password with 182 queries.
6 Correct 2 ms 208 KB Guessed the password with 223 queries.
7 Correct 67 ms 332 KB Guessed the password with 5477 queries.
8 Correct 145 ms 344 KB Guessed the password with 10742 queries.
9 Correct 194 ms 340 KB Guessed the password with 16434 queries.
10 Correct 285 ms 348 KB Guessed the password with 21089 queries.
11 Incorrect 864 ms 336 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 208 KB Guessed the password with 146 queries.
2 Correct 3 ms 208 KB Guessed the password with 315 queries.
3 Correct 2 ms 208 KB Guessed the password with 52 queries.
4 Correct 3 ms 272 KB Guessed the password with 120 queries.
5 Correct 2 ms 336 KB Guessed the password with 182 queries.
6 Correct 2 ms 208 KB Guessed the password with 223 queries.
7 Correct 67 ms 332 KB Guessed the password with 5477 queries.
8 Correct 145 ms 344 KB Guessed the password with 10742 queries.
9 Correct 194 ms 340 KB Guessed the password with 16434 queries.
10 Correct 285 ms 348 KB Guessed the password with 21089 queries.
11 Incorrect 864 ms 336 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -