oj.uz

Submission #664282

# Submission time Handle Problem Language Result Execution time Memory
664282 2022-11-27T07:02:45 Z Nursik Password (RMI18_password) C++14
50 / 100
 1147 ms 472 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 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;
            if ((int)ans.size() == n){
                break;
            }
        }
        if ((int)ans.size() == n)
            break;
    }
    return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 1 ms 208 KB Guessed the password with 181 queries.
4 Correct 3 ms 300 KB Guessed the password with 216 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 348 KB Guessed the password with 4788 queries.
2 Correct 84 ms 324 KB Guessed the password with 10281 queries.
3 Correct 211 ms 340 KB Guessed the password with 13667 queries.
4 Correct 357 ms 348 KB Guessed the password with 20689 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 1 ms 208 KB Guessed the password with 181 queries.
6 Correct 3 ms 300 KB Guessed the password with 216 queries.
7 Correct 70 ms 348 KB Guessed the password with 4788 queries.
8 Correct 84 ms 324 KB Guessed the password with 10281 queries.
9 Correct 211 ms 340 KB Guessed the password with 13667 queries.
10 Correct 357 ms 348 KB Guessed the password with 20689 queries.
11 Correct 1043 ms 352 KB Guessed the password with 49512 queries.
12 Correct 257 ms 460 KB Guessed the password with 19157 queries.
13 Correct 792 ms 348 KB Guessed the password with 47683 queries.
14 Correct 310 ms 348 KB Guessed the password with 26326 queries.
15 Correct 824 ms 456 KB Guessed the password with 44836 queries.
16 Correct 325 ms 472 KB Guessed the password with 24336 queries.
17 Execution timed out 1147 ms 352 KB Time limit exceeded (wall clock)
18 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 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 1 ms 208 KB Guessed the password with 181 queries.
6 Correct 3 ms 300 KB Guessed the password with 216 queries.
7 Correct 70 ms 348 KB Guessed the password with 4788 queries.
8 Correct 84 ms 324 KB Guessed the password with 10281 queries.
9 Correct 211 ms 340 KB Guessed the password with 13667 queries.
10 Correct 357 ms 348 KB Guessed the password with 20689 queries.
11 Correct 1043 ms 352 KB Guessed the password with 49512 queries.
12 Correct 257 ms 460 KB Guessed the password with 19157 queries.
13 Correct 792 ms 348 KB Guessed the password with 47683 queries.
14 Correct 310 ms 348 KB Guessed the password with 26326 queries.
15 Correct 824 ms 456 KB Guessed the password with 44836 queries.
16 Correct 325 ms 472 KB Guessed the password with 24336 queries.
17 Execution timed out 1147 ms 352 KB Time limit exceeded (wall clock)
18 Halted 0 ms 0 KB -