oj.uz

Submission #664132

# Submission time Handle Problem Language Result Execution time Memory
664132 2022-11-27T06:27:12 Z Nursik Password (RMI18_password) C++14
50 / 100
 1291 ms 296 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 = "";
            for (int j = 0; j <= len; ++j){
                string add = "";
                int lol = 0;
                while (1 && is[i] > 0){
                    add += ch;
                    string q = "";
                    for (int k = 0; k < j; ++k){
                        q += ans[k];
                    }
                    q += add;
                    for (int k = j; k < len; ++k){
                        q += ans[k];
                    }
                    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];
            }
            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 2 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 1 ms 208 KB Guessed the password with 117 queries.
3 Correct 2 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 43 ms 292 KB Guessed the password with 4789 queries.
2 Correct 150 ms 288 KB Guessed the password with 10282 queries.
3 Correct 225 ms 288 KB Guessed the password with 13668 queries.
4 Correct 417 ms 296 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 2 ms 208 KB Guessed the password with 187 queries.
3 Correct 1 ms 208 KB Guessed the password with 53 queries.
4 Correct 1 ms 208 KB Guessed the password with 117 queries.
5 Correct 2 ms 208 KB Guessed the password with 181 queries.
6 Correct 3 ms 208 KB Guessed the password with 217 queries.
7 Correct 43 ms 292 KB Guessed the password with 4789 queries.
8 Correct 150 ms 288 KB Guessed the password with 10282 queries.
9 Correct 225 ms 288 KB Guessed the password with 13668 queries.
10 Correct 417 ms 296 KB Guessed the password with 20690 queries.
11 Execution timed out 1291 ms 296 KB Time limit exceeded (wall clock)
12 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 2 ms 208 KB Guessed the password with 187 queries.
3 Correct 1 ms 208 KB Guessed the password with 53 queries.
4 Correct 1 ms 208 KB Guessed the password with 117 queries.
5 Correct 2 ms 208 KB Guessed the password with 181 queries.
6 Correct 3 ms 208 KB Guessed the password with 217 queries.
7 Correct 43 ms 292 KB Guessed the password with 4789 queries.
8 Correct 150 ms 288 KB Guessed the password with 10282 queries.
9 Correct 225 ms 288 KB Guessed the password with 13668 queries.
10 Correct 417 ms 296 KB Guessed the password with 20690 queries.
11 Execution timed out 1291 ms 296 KB Time limit exceeded (wall clock)
12 Halted 0 ms 0 KB -