oj.uz

Submission #664143

# Submission time Handle Problem Language Result Execution time Memory
664143 2022-11-27T06:29:23 Z Nursik Password (RMI18_password) C++14
50 / 100
 1145 ms 464 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();
            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 && is[i] > 0){
                    add += ch;
                    string q = pref;
                    q += add;
                    q += suff;
                    if ((int)q.size() > n)
                        break;
                    int kek = query(q);
                    if (kek == len + lol + 1){
                        lol += 1;
                        nans += ch;
                        is[i] -= 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 208 KB Guessed the password with 76 queries.
2 Correct 4 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 53 queries.
2 Correct 2 ms 208 KB Guessed the password with 117 queries.
3 Correct 3 ms 208 KB Guessed the password with 181 queries.
4 Correct 3 ms 208 KB Guessed the password with 217 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 324 KB Guessed the password with 4789 queries.
2 Correct 138 ms 448 KB Guessed the password with 10282 queries.
3 Correct 168 ms 316 KB Guessed the password with 13668 queries.
4 Correct 226 ms 340 KB Guessed the password with 20690 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 4 ms 208 KB Guessed the password with 187 queries.
3 Correct 1 ms 208 KB Guessed the password with 53 queries.
4 Correct 2 ms 208 KB Guessed the password with 117 queries.
5 Correct 3 ms 208 KB Guessed the password with 181 queries.
6 Correct 3 ms 208 KB Guessed the password with 217 queries.
7 Correct 54 ms 324 KB Guessed the password with 4789 queries.
8 Correct 138 ms 448 KB Guessed the password with 10282 queries.
9 Correct 168 ms 316 KB Guessed the password with 13668 queries.
10 Correct 226 ms 340 KB Guessed the password with 20690 queries.
11 Correct 1022 ms 464 KB Guessed the password with 49513 queries.
12 Correct 218 ms 452 KB Guessed the password with 19158 queries.
13 Correct 872 ms 352 KB Guessed the password with 47684 queries.
14 Correct 352 ms 336 KB Guessed the password with 26327 queries.
15 Correct 868 ms 344 KB Guessed the password with 44836 queries.
16 Correct 348 ms 348 KB Guessed the password with 24337 queries.
17 Runtime error 1145 ms 460 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 208 KB Guessed the password with 76 queries.
2 Correct 4 ms 208 KB Guessed the password with 187 queries.
3 Correct 1 ms 208 KB Guessed the password with 53 queries.
4 Correct 2 ms 208 KB Guessed the password with 117 queries.
5 Correct 3 ms 208 KB Guessed the password with 181 queries.
6 Correct 3 ms 208 KB Guessed the password with 217 queries.
7 Correct 54 ms 324 KB Guessed the password with 4789 queries.
8 Correct 138 ms 448 KB Guessed the password with 10282 queries.
9 Correct 168 ms 316 KB Guessed the password with 13668 queries.
10 Correct 226 ms 340 KB Guessed the password with 20690 queries.
11 Correct 1022 ms 464 KB Guessed the password with 49513 queries.
12 Correct 218 ms 452 KB Guessed the password with 19158 queries.
13 Correct 872 ms 352 KB Guessed the password with 47684 queries.
14 Correct 352 ms 336 KB Guessed the password with 26327 queries.
15 Correct 868 ms 344 KB Guessed the password with 44836 queries.
16 Correct 348 ms 348 KB Guessed the password with 24337 queries.
17 Runtime error 1145 ms 460 KB Execution killed with signal 13
18 Halted 0 ms 0 KB -